线段树二分

问题描述

维护长度为 \(n\) 的序列 \(a\)，支持以下操作：

• 1 i x：把 \(a_i\) 修改为 \(x\)。
• 2 i x：询问最小的 \(j\) 满足 \(j>=i\) 且 \(a_j>=x\)。

\(1\leq n \leq 10^6\)

解决方法

在线段树外直接二分可以做到 \(O(n\log^2n)\) 的时间复杂度，加上简单的剪枝可能效率会高一些，但都无法光明正大地通过这道题。

考虑直接在线段树上二分。叶子节点就直接返回，对于非叶子节点，如果左儿子在查询区间内且左儿子的最大权值大于等于查询的值，就先往左儿子查询，查到了就直接返回，然后再往右儿子查询。

代码：

int query(int u, int x, int k)
{
	if(t[u].a == t[u].b) return t[u].v > k ? t[u].a : N; // v 表示节点代表的区间的最大值
	int ls = u << 1, rs = ls | 1, res = N;
	if(t[ls].b >= x && t[ls].v > k) res = query(ls, x, k);
	if(res < N) return res;
	if(t[rs].v > k) res = query(rs, x, k);
	return res;
}

时间复杂度分析

最坏的情况应该是这样的：从根节点到一个节点，先往左儿子走并且没找到，然后往右儿子走并找到了。从根节点到当前节点的过程中，它不可能存在往左儿子走但找不到，因为如果是这样这个当前节点的区间一定是被查询区间完全包含的，不会有尝试但不能找到，时间复杂度 \(O(\log n)\)；递归左儿子但没有答案，说明左儿子中大于查询的值的位置是在查询区间左边的，所以它只会往左儿子递归，则时间复杂度是 \(O(\log n)\)；往右儿子走之后，节点区间会被完全包含在查询区间里面，所以后面走的路径一定可以找到答案，时间复杂度是 \(O(\log n)\)。综上，单次查询的时间复杂度是 \(O(\log n)\) 的。

其它应用

CF19D：查询一个点右上角最左边最下边的点。与原问题相似，只需加上离散化并用 set 维护即可。

查询序列第 \(i\) 个位置后面第一段连续的长度为 \(k\) 的 1。

其它任何你能想到的用线段树维护的东西基本上都可以套上线段树二分的模型。