线段树上二分：从 O(log²n) 到 O(log n)
在处理区间查询问题时，我们常遇到这样的需求：在给定区间内快速定位第一个（或最后一个）满足某种条件的位置。例如，在区间 [l, r] 中找出第一个值大于 x 的元素下标。朴素做法是结合二分查找与线段树查询，但每次 check 操作需要 O(log n) 时间，总复杂度为 O(log²n)。
本文介绍一种更高效的技巧——**在线段树结构内部直接进行二分决策**，将时间复杂度优化至 O(log n)。
核心思想
传统方法是在外层二分位置，并对每个候选位置调用线段树查询其对应区间的最大值/最小值等信息。而本优化的关键在于：**利用线段树本身的结构，在递归过程中根据左右子树的信息直接决定走向哪一侧**，避免重复查询。
具体来说：
- 若当前节点维护的区间完全包含于目标查询区间，则可直接依据左、右子树的最大值判断下一步方向；
- 否则按标准线段树遍历方式进入与其相交的子区间；
- 在每一步都提前判断是否存在可行解，若整个子树都不满足条件则立即返回 -1。
基础版本：全局首个大于 x 的位置
假设我们要在 [1, n] 范围内找到第一个值大于 x 的下标：
int find_first(int u, int x) {
// 整个区间的最大值都不超过x，无解
if (tree[u].max_val <= x) return -1;
// 叶子节点，说明找到了答案
if (tree[u].l == tree[u].r) return tree[u].l;
// 根据左子树是否存在解来决定走向
if (tree[u * 2].max_val > x)
return find_first(u * 2, x);
else
return find_first(u * 2 + 1, x);
}
该过程仅沿一条路径向下，故时间复杂度为 O(log n)。
扩展到任意区间 [l, r]
当查询范围受限于 [L, R] 时，需区分三种情况：
- 当前节点区间完全被 [L, R] 包含 → 可以在此节点上做二分决策；
- 部分重叠 → 继续递归到与 [L, R] 相交的子节点；
- 无交集 → 忽略。
实现如下：
int query_range(int u, int L, int R, int x) {
// 提前剪枝：本子树无有效解
if (tree[u].max_val <= x) return -1;
if (tree[u].l == tree[u].r)
return tree[u].l;
int mid = (tree[u].l + tree[u].r) >> 1;
// 完全包含于查询区间：允许内部二分
if (L <= tree[u].l && tree[u].r <= R) {
if (tree[u * 2].max_val > x)
return query_range(u * 2, L, R, x);
else
return query_range(u * 2 + 1, L, R, x);
}
// 部分相交：分别尝试左右子树
else {
int res = -1;
if (L <= mid)
res = query_range(u * 2, L, R, x);
if (res == -1 && R > mid)
res = query_range(u * 2 + 1, L, R, x);
return res;
}
}
注意：**必须在函数入口处判断 max_val ≤ x 的情况**，否则可能导致多个无效子树被完整遍历，使最坏复杂度退化为 O(log²n)。
寻找最右侧满足条件的位置
只需调整优先访问顺序，让系统尽量往右走即可：
int query_rightmost(int u, int L, R, int x) {
if (tree[u].max_val <= x) return -1;
if (tree[u].l == tree[u].r)
return tree[u].l;
int mid = (tree[u].l + tree[u].r) >> 1;
if (L <= tree[u].l && tree[u].r <= R) {
// 优先检查右子树
if (tree[u * 2 + 1].max_val > x)
return query_rightmost(u * 2 + 1, L, R, x);
else
return query_rightmost(u * 2, L, R, x);
} else {
int res = -1;
if (R > mid)
res = query_rightmost(u * 2 + 1, L, R, x);
if (res == -1 && L <= mid)
res = query_leftmost(u * 2, L, R, x);
return res;
}
}
注意事项
- 涉及懒更新时，务必在进入子节点前执行 pushdown 操作；
- 所有递归入口均应包含有效性判断，防止无效分支展开；
- 此方法适用于支持区间合并性质的问题，如最大值、最小值、和等单调性信息。
典型应用题单
