各位OIer大家好，蒟蒻在这里献丑了。

书接上回，基础篇已然结束，但不会修改和查询的线段树不是一个好的线段树

线段树求值

探讨完线段树是什么，我们再来思考一下线段树怎么求值

求值的前提

并不是所有的区间操作的题都适合线段树（不然太逆天了），事实上，线段树能做的题通常都要满足区间加法的性质
什么是区间加法？我所说的区间加法是指广义上的。这里我举几个例子：

• 求区间的最值（最大&最小）
• 求区间的和&积
• 求区间的最大公约数/最小公倍数

不难发现，这些例子基本上都能拆成几个小的子问题来求解，但以下问题不能用线段树求：

• 众数
• 01序列中最长的连续0/1

这些问题不能拆成几个小的区间进行操作，所以线段树不能或很难去求

如何求值

请看下图

现在要求区间[2,5]的值，如何求呢？

我们可以发现，我们要求的区间[2,5]正好包含在树[1,5]中，所以要求的值肯定在这个序列里

接下来，子树分成了[1,3]和[4,5]两个区间，因为[4,5]包含在要求的[2,5]当中，所以它的值可以作为构成整个区间答案的一部分，即[2,5]的值一定由[4,5]的值和其他区间的值构成

右树考虑完了，再考虑左树。显然，整个区间[1,3]相对于剩下要求的[2,3]还是太大了，那么再考虑[1,3]的子树[1,2]和[3,3]。

左树[1,2]还得再分成[1,1]和[2,2]，这样[2,2]的值就能求出来，右树[3,3]的值也能得出来。

这样，要求的区间[2,5]就可以转化为[2,2] [3,3] [4,5]，它们三个的值就可以共同构建成整个区间的值

代码（以求区间最大值为例）

int query(int u,int l,int r,int x,int y){
    if(l>=x&&r<=y) //整个区间被包含在要求的区间内
        return tr[u].ans; //返回该区间的值
    int mid=l+r>>1,ans=-0x3f3f3f3f; //寻找左右子树
    if(x<=mid) //左边子树包含要求的值
        ans=query(u<<1,l,mid,x,y); //求值
    if(y>mid) //右边子树包含要求的值
        ans=max(query(u<<1|1,mid+1,r,x,y),ans); //得出左右子树最大值
    return ans;
}

线段树修改

单点修改

最简单的方法就是重新建一棵树覆盖掉原来的，但时间冗余，所以可以只找到那个点并修改，再一步步向上更新。

（因为单点修改太简单，直接上代码）

// 以求区间最大值为例
void push_up(int u){
    tr[u].ans=max(tr[u<<1].ans,tr[u<<1|1].ans); //父节点的值用左右两子树的值更新
}

void modify(int u,int l,int r,int x,int y){
    if(l==x&&r==x){ //找到那个点了
        tr[u].ans=y; //修改
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) //在左子树
        modify(u<<1,l,mid,x,y);
    else //在右子树
        modify(u<<1|1,mid+1,r,x,y);
    push_up(u); //更新父节点
}

下一讲：区间修改&懒标记（未完待续）