线段树模板

线段树是一种二叉搜索树，将一个区间化分成多个单元区间，其中树的每个叶子就是对应的每个单元区间。

基本思想：二分

定义

1 const int maxx=50005;
2 int a[maxx],mx[maxx*4],lazy[maxx*4];
3 //数组a为原数组，数组mx为线段树维护区间和，数组lazy为懒惰标记

更新节点信息

1 void pushup(int rt)
2 {
3     mx[rt]=mx[rt*2]+mx[tr*2+1];
4 }

建立线段树

 1 void build(int l,int r,int rt)
 2 {
 3     if(l==r)
 4     {
 5         mx[rt]=a[l];
 6         return ;
 7     }
 8     int mid=(l+r)/2;
 9     build(l,mid,rt*2);
10     build(mid+1,r,rt*2+1);
11     pushup(rt);
12 }

下推懒惰标记

 1 void pushdown(int k,int l,int r)//l表示左子树节点个数，r表示右子树节点个数
 2 {
 3     if(lazy[k])
 4     {
 5         mx[k*2]+=lazy[k]*l;
 6         mx[k*2+1]+=lazy[k]*r;
 7         lazy[k*2]+=lazy[k];
 8         lazy[k*2+1]+=lazy[k];
 9         lazy[k]=0;
10     }
11 }

更新点

 1 void updata(int L,int l,int r,int rt,int val)
 2 {
 3     if(l==r)//到达所要求的点
 4     {
 5         mx[rt]+=val;
 6         return ;
 7     }
 8     int mid=(l+r)/2;
 9     if(L<=mid)//往上或者往下
10         updata(L,l,mid,rt*2,val);
11     else
12         updata(L,mid+1,r,tr*2+1,val);
13     pushup(rt);
14 }

更新区间

 1 void updata(int L,int l,int r,int rt,int val)
 2 {
 3     if(l==r)//到达所要求的点
 4     {
 5         mx[rt]+=val;
 6         return ;
 7     }
 8     int mid=(l+r)/2;
 9     pushdown(rt,mid-l+1,r-mid);
10     if(L<=mid)//往上或者往下
11         updata(L,l,mid,rt*2,val);
12     else
13         updata(L,mid+1,r,tr*2+1,val);
14     pushup(rt);
15 }

区间查询

 1 int query(int L,int R,int l,int r,int rt)
 2 {
 3     if(L<=l&&r<=R)//在范围里
 4         return mx[rt];
 5     int mid=(l+r)/2;
 6     pushdown(rt,mid-l+1,r-mid);//点更新忽略这个
 7     int ans=0;
 8     if(L<=mid)//可以再往下
 9         ans+=query(L,R,l,mid,rt*2);
10     if(R>mid)//可以再往上
11         ans+=query(L,R,mid+1,rt*2+1);
12     return ans;
13 }

先将模板写下来，以后再来总结