线段树二分

统计零的数量，并寻找第 $k$ 个零

这个问题要求：

• 求给定区间中零的数量；
• 使用另一个函数求第 $k$ 个零的下标。

同样，我们只需要稍微修改树中保存的值：

这一次，在 t[] 中保存每个区间中零的数量。

如何实现 build、update 和 count_zero 函数是非常直接的，可以直接使用区间求和问题中的方法。

因此，问题的第一部分已经解决。

现在学习如何求数组 $a[]$ 中第 $k$ 个零。

为了完成这个任务，我们从根节点开始沿线段树向下移动，每一次根据第 $k$ 个零位于哪个区间，选择进入左子节点或右子节点。

为了判断应该进入哪个子节点，只需要查看左子节点对应区间中零的数量。

如果预先计算出的这个数量大于等于 $k$，那么应该进入左子节点。

否则进入右子节点。

注意，如果选择进入右子节点，需要从 $k$ 中减去左子节点中零的数量。

在实现中，如果数组 $a[]$ 中的零少于 $k$ 个，可以通过返回 $-1$ 处理这种特殊情况。

int find_kth(int v, int tl, int tr, int k) {
    if (k > t[v])
        return -1;
    if (tr - tl == 1)
        return tl;
    int tm = (tl + tr) / 2;
    if (t[v*2] >= k)
        return find_kth(v*2, tl, tm, k);
    else
        return find_kth(v*2+1, tm, tr, k - t[v*2]);
}

---

查找前缀和达到给定值的位置

问题如下：

给定值 $x$，需要快速找到最小的下标 $i$，使数组 $a[]$ 前 $i$ 个元素的和大于等于 $x$。

这里假设数组 $a[]$ 中只包含非负数。

这个问题可以利用二分查找解决，在二分过程中使用线段树计算前缀和。

不过，这会得到一个

$$O(\log^2 n)$$

的算法。

实际上，可以使用上一节中相同的思想，通过在线段树上向下移动直接找到位置：

每一步根据左子节点的区间和，决定进入左子树还是右子树。

这样可以在

$$O(\log n)$$

时间内得到答案。

---

查找第一个大于给定值的元素

问题如下：

给定一个值 $x$ 和区间

$$a[l\dots r),$$

找出这个区间中最小的下标 $i$，使得

$$a[i]>x.$$

可以利用线段树的区间最大值查询配合二分搜索解决，但这样会得到

$$O(\log^2 n)$$

的算法。

实际上，可以使用与前面相同的思想：

直接在线段树上向下搜索，每一步根据左子节点的最大值决定进入左子树还是右子树。

这样就能在

$$O(\log n)$$

时间内找到答案。

int get_first(int v, int tl, int tr, int l, int r, int x) {
    if (r <= tl || tr <= l) return -1;
    if(t[v] <= x) return -1;

    if (tr - tl == 1) return tl;

    int tm = tl + (tr-tl)/2;
    int left = get_first(2*v, tl, tm, l, r, x);
    if(left != -1) return left;
    return get_first(2*v+1, tm, tr, l ,r, x);
}