线段树整理

线段树模板

这是合并。可以改的，如果改成求最值，只要将赋值变成，min或max就ok了。

1 void update(int rt)
2 {
3     sum[rt] = sum[rt*2] + sum[rt*2+1] ;
4 }

------------这是建立一颗线段树，l左端点，r右端点，rt第几条线段------------------

 1 void build(int l,int r,int rt) //建立
 2 {
 3     if(l==r)
 4     {
 5         sum[rt] = a[l] ;  //sum[rt] = a[r];
 6         return ;
 7     }
 8     int m = (l+r) >> 1;
 9     build(l,m,rt*2);
10     build(m+1,r,rt*2+1);
11     update(rt) ;
12 }

-----------------------------改变将第 p 个数个改为 v -------------------------

 1 void modify(int l,int r,int rt,int p,int v) //改变
 2 {
 3     if(l==r)
 4     {
 5         sum[rt] = v;
 6         return ;
 7     }
 8     int m = (l+r) >> 1;
 9     if(p<=m) modify(l,m,rt*2,p,v);    
10     else modify(m+1,r,rt*2+1,p,v);
11     update(rt);
12 }

----------------访问 nowl 左端点，nowr 右端点，求此区间的 sum 值；-------------

 1 int query(int l,int r,int rt,int nowl,int nowr) //访问 (注意是int类型函数)
 2 {
 3     if(nowl<=l && r<=nowr)        //如果区间包含在[l,r]在访问的区间里，加上它 
 4     {
 5         return sum[rt];
 6     }
 7     int ans=0;
 8     int m = (l+r) >> 1;
 9     if(nowl<=m) ans+=query(l,m,rt*2,nowl,nowr);      //在左边寻找 
10     if(nowr>m) ans+=query(m+1,r,rt*2+1,nowl,nowr);     //在右边寻找 
11     return ans;
12 }