线段树上二分学习笔记

· · 算法·理论

update: 题面描述不准确，原题是一个 |(a_i-a_{i-1})|\le 1 的函数，也就是说是一条曲线。

在 NOIP 模拟赛里，我遇到了这么一道题：

给你一个相邻两位相差为一的序列，支持两种操作：

  1. 给区间 [l, r] 加上一个值。
  2. 查询区间 [l, r] 中第一个等于 x 的下标，保证原序列满足 |(a_i-a_{i-1})|\le 1 。

当时在考场上，我虽然想到了二分，但没想到最小值具有单调性，结果坠机了。考完以后，我琢磨出了一个做法：先暴力建一棵线段树，然后在这棵树上二分找第一个大于等于 x 的数。不过这样时间复杂度是 O(\log^2 n)，明显不优。如果换成其他 RMQ 结构，虽然查询快，但区间修改又不方便了。这时候就需要我们的主角——线段树上二分。

换个更形象的说法，其实就是在线段树上游走。基本思路就是直接利用左右子树的信息，判断答案可能在左边还是右边，然后直接往可能有解的那边走。对于查询区间 [l,r]，我们只需要像普通线段树查询一样，只处理和目标区间有交集的节点。如果一个节点区间没有被完全包含在目标区间里，那它就不能直接给出答案，得继续往下找。

例题

这道题跟我上面说的差不多，就是多了点小细节。

参考代码

int query(int p,int l,int r,int x)
{
    if(tr[p].mn>x) 
        return INF;// 当前区间最小值都比x大，肯定没戏
    if(tr[p].l==tr[p].r)// 走到叶子了
        return tr[p].mn<=x?tr[p].l:INF; // 看看这个点行不行
    if(tr[id].l>=l&&tr[p].r<=r)
    { // 这个节点完全在查询区间里
        if(tr[lt].mn<=x) 
            return query(rt,l,r,x); // 左边可能有答案
        else 
            return query(rt,l,r,x); // 左边不行就去右边
    }
    int ans=INF,mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid)
        ans=query(lt,l,r,x); // 左边跟查询区间有重叠,优先找i左边
    if(ans==INF&&r>mid) 
        ans=query(rt,l,r,x); // 左边没找到且右边有重叠
    return ans;
}

总结

线段树上二分其实就是在线段树的子树里中进行即使决策，优先往左边走，只处理跟查询区间有交集的节点，这样就能高效地找到答案。