宅男唱着歌-桥边菇凉

------------恢复内容开始------------

暂无

线段树是所有 RMQ 中最常用的数据结构。

功能：区间修改区间查询。不止最值、求和。只要可递推的值都可以构造线段树。

如果区间大小为 n，线段树有 cnt 个节点，那么 2n−1≤cnt<4n。

节点

对于每个节点 x，和堆类似，父亲节点为 x>>1（即 x/2 下取整的位运算方法，位运算方便而且快），左儿子为 x<<1（即 2x），右儿子为 x<<1|1（即 2x+1）。

同时每个节点对应一段区间，所以叫线段树。节点 1 对应的区间为 1∼n。设一个节点对应的区间为 l∼r，那么它的左儿子对应的区间就是 l∼mid，其中 mid=(l+r)>>1，右儿子区间为 mid+1∼r。如果一个节点对应单点区间，就没有儿子。

同时每个节点对应一个值，即该区间的 RMQ 值。如果是求最值问题，就表示该区间最大值；如果是求和问题，就表示该区间的和。

操作（单点修改区间查询）

一个线段树是求和还是求最值或者求别的东西，取决于 pushup(k) 函数，其中 k 为节点编号，时间复杂度 O(1)。

void pushup(int k){v[k]=max(v[k<<1],v[k<<1|1]);}//求最大值

根据原序列构造初始的线段树用 build() 函数，单点节点上的值就为单点的值，递归从下到上构造，时间复杂度 O(nlogn)。

void build(int k=1,int l=1,int r=n){//表示外部应用默认k=1,l=1,r=n

if(l==r){v[k]=a[l];return;} //单点节点

build(k<<1,l,mid),build(k<<1|1,mid+1,r); //递归构造

pushup(k); //递推

}

先讲单点修改（加上 y），只需与 build() 函数类似的递归操作即可，如果到达单点节点，就修改，不走那些跟查询单点没关系的区间、别忘了修改完后也要递推，时间复杂度 O(logn)。

void fix(int x,int y,int k=1,int l=1,int r=n){

if(l==x&&r==x){v[k]+=y;return;} //单点修改

if(mid>=x) fix(x,y,k<<1,l,mid); //递归左儿子

else fix(x,y,k<<1|1,mid+1,r); //递归右儿子

pushup(k);//递推

}

区间查询，如果单前节点在查询区间内，就返回值。否则，递归左儿子右儿子，递推得区间查询值。时间复杂度 O(logn)，因为只会走相关的 logn 个节点。

int fmax(int x,int y,int k=1,int l=1,int r=n){

if(x<=l&&r<=y) return v[k]; //在查找区间内，返回值

int res=0;

if(mid>=x) res=max(res,fmax(x,y,k<<1,l,mid));

if(mid<y) res=max(res,fmax(x,y,k<<1|1,mid+1,r));

return res;

}

总时间复杂度 O(nlogn) ，全代码：

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,m,a[N];

namespace Sumtree{

#define mid ((l+r)>>1)

int v[N<<2];

void pushup(int k){v[k]=max(v[k<<1],v[k<<1|1]);}

void build(int k=1,int l=1,int r=n){

if(l==r){v[k]=a[l];return;}

build(k<<1,l,mid),build(k<<1|1,mid+1,r);

pushup(k);

}

void fix(int x,int y,int k=1,int l=1,int r=n){

if(l==x&&r==x){v[k]+=y;return;}

if(mid>=x) fix(x,y,k<<1,l,mid);

else fix(x,y,k<<1|1,mid+1,r);

pushup(k);

}

int fmax(int x,int y,int k=1,int l=1,int r=n){

if(x<=l&&r<=y) return v[k];

int res=0;

if(mid>=x) res=max(res,fmax(x,y,k<<1,l,mid));

if(mid<y) res=max(res,fmax(x,y,k<<1|1,mid+1,r));

return res;

}

#undef mid

}using namespace Sumtree;

int main(){

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

scanf("%d",a+i);

build();

for(int i=1,x,y,z;i<=m;i++){

scanf("%d%d%d",&x,&y,&z);

if(x==1) fix(y,z);

else printf("%d\n",fmax(y,z));

}

return 0;

}

线段树如果只能单点修改区间查询，代码还这么长，就没人用他了。所以可想而知，线段树还可以区间修改，区间查询。

------------恢复内容结束------------