相关讲解资料：

 

树状数组： (线段树预备)

线段树讲解：

　　　　初学版：

　　　　进阶完整版：

 

代码：

 

完整注释模板一张，参(chao)考(xi)楼上的博客

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;#define mid (l+r)/2#define lson (pos<<1)#define rson ((pos<<1)|1)#define maxn 100007 //元素个数ll n,m;ll root=1;ll arr[maxn];ll Lazy[maxn<<2];//区间增加的lazy标记/*其目的是： 为防止修改区间总结点对每个子节点都要进行修改，导致复杂度爆炸 暂时记录一下这个区间总结点的所有子树都“待修改” 如果用到下面的子节点就修改，下推lazy标志，用不到就不管 以此来减少复杂度*/ll sum[maxn<<2];//线段树求和最多分成4个子区间void PushUp(long long pos)//暂时写成求和函数，可以自由变换{ sum[pos]=sum[lson]+sum[rson]; //用数组表示二叉树:假设某个节点的编号为v,那么它的左子节点编号为2*v，右子节点编号为2*v+1,规定根节点为1 //通常2*v写成v<<1 , 2*v+1写成v<<1|1;}void PushDown(long long pos,long long l,long long r)//区间查询用{ //l,r为左子树，右子树的数字区间 if(Lazy[pos]) { //修改子节点的增加数 Lazy[lson]+=Lazy[pos]; Lazy[rson]+=Lazy[pos]; //修改子节点区间的sum sum[lson]+=Lazy[pos]*(mid-l+1); sum[rson]+=Lazy[pos]*(r-(mid+1)+1); //清除本节点标记 Lazy[pos]=0; }}void Build(long long l,long long r,long long pos)//[l,r]表示当前节点区间，pos表示当前节点的实际存储位置{ if(l==r)//如果到达儿子节点，存储并返回 { sum[pos]=arr[l]; return; } Build(l,mid,pos<<1); Build(mid+1,r,pos<<1|1); PushUp(pos);}void UpPoint(long long pos,long long l,long long r,long long L,long long C)//对单点修改{ //L表示要修改的点编号，[l,r]表示当前区间，pos是当前节点编号; if(l==r)//到达儿子节点之后就修改 { sum[pos]+=C; return; } //根据条件判断往左子树调用还是往右 if(L<=mid) UpPoint(lson,l,mid,L,C); else UpPoint(rson,mid+1,r,L,C); PushUp(pos);//子节点更新之后本节点也需要更新;}void UpZone(long long pos,long long l,long long r,long long L,long long R,long long C)//对整个区间进行修改{ //L,R表示操作区间 , l,r表示当前节点区间 , pos表示当前节点编号 if(L<=l && R>=r)//节点区间在操作区间之内，直接返回 { sum[pos]+=C*(r-l+1);//这个点需要加上区间长度*C Lazy[pos]+=C;//用Lazy标记，表示本区间的Sum正确，子区间的Sum仍需要根据Add调整 return; } PushDown(pos,l,r);//下推标记 if(L<=mid) UpZone(lson,l,mid,L,R,C); if(R>mid) UpZone(rson,mid+1,r,L,R,C); PushUp(pos);}ll Query(long long l,long long r,long long L,long long R,long long pos){ //L,R表示操作区间 , l,r表示当前节点区间 , pos表示当前节点编号 if(L<=l && R>=r)//节点区间在操作区间之内，直接返回 { return sum[pos]; } PushDown(pos,l,r);//下推标记，否则sum可能不正确 //统计答案 long long ans=0; if(L<=mid) ans+=Query(l,mid,L,R,lson); if(R>mid) ans+=Query(mid+1,r,L,R,rson); PushUp(pos); return ans;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { long long tmp; cin>>tmp; UpZone(root,1,n,i,i,tmp); } for(int j=1;j<=m;j++) { long long a,b,c,d; cin>>a; if(a==1) { cin>>b>>c>>d; UpZone(root,1,n,b,c,d); } else { cin>>b>>c; cout<
            
             <
            
           
          
         
        
       
      
     

下面是动态开点的模板：

1. 不能define lson，rson，也不能用pos<<1和pos<<1|1，否则就失去了“动态开点”的意义

2. Get_Son和UpZone要&引用

3. 尽量开long long，也好调

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;//！！！！！！！！！//Get_Son和UpZone要&引用//不能define lson，rson，也不能用pos<<1和pos<<1|1//！！！！！！！！！#define mid (l+r)/2#define maxn 1000007 //元素个数ll n,m;ll root=1,cnt=1;ll lson[maxn],rson[maxn];ll Lazy[maxn<<2];//区间增加的lazy标记/*其目的是： 为防止修改区间总结点对每个子节点都要进行修改，导致复杂度爆炸 暂时记录一下这个区间总结点的所有子树都“待修改” 如果用到下面的子节点就修改，下推lazy标志，用不到就不管 以此来减少复杂度*/ll sum[maxn<<2];//线段树求和最多分成4个子区间ll Get_Son(long long &pos){ if(pos==0) pos=++cnt; return pos;}void PushUp(long long pos){ sum[pos]=sum[lson[pos]]+sum[rson[pos]]; //用数组表示二叉树:假设某个节点的编号为v,那么它的左子节点编号为2*v，右子节点编号为2*v+1,规定根节点为1 //通常2*v写成v<<1 , 2*v+1写成v<<1|1;}void PushDown(long long pos,long long l,long long r)//区间查询用{ //l,r为左子树，右子树的数字区间 // if(Lazy[pos]==0) return; // if(r-l<=1) return; // if(pos<<1!=0) // { // pos<<1=++cnt; // sum[pos<<1]+=(mid-l+1)*Lazy[pos]; // Lazy[pos<<1]+=Lazy[pos]; // } // if(rson[pos]!=0) // { // rson[pos]=++cnt; // sum[rson[pos]]+=(r-mid+1)*Lazy[pos]; // Lazy[rson[pos]]+=Lazy[pos]; // } sum[Get_Son(lson[pos])]+=(mid-l+1)*Lazy[pos]; sum[Get_Son(rson[pos])]+=(r-mid)*Lazy[pos]; Lazy[lson[pos]]+=Lazy[pos]; Lazy[rson[pos]]+=Lazy[pos]; Lazy[pos]=0;}void UpZone(long long &pos,long long l,long long r,long long L,long long R,long long C){ //L,R表示操作区间 , l,r表示当前节点区间 , pos表示当前节点编号 if(pos==0) pos=++cnt; if(Lazy[pos]!=0) PushDown(pos,l,r);//下推标记 if(L<=l && R>=r)//节点区间在操作区间之内，直接返回 { sum[pos]+=(r-l+1)*C;//这个点需要加上区间长度*C Lazy[pos]+=C;//用Lazy标记，表示本区间的Sum正确，子区间的Sum仍需要根据Lazy调整 return; } if(L<=mid) UpZone(lson[pos],l,mid,L,R,C); if(R>mid) UpZone(rson[pos],mid+1,r,L,R,C); PushUp(pos);}ll Query(long long pos,long long l,long long r,long long L,long long R){ //L,R表示操作区间 , l,r表示当前节点区间 , pos表示当前节点编号 if(pos==0) return 0; if(Lazy[pos]) PushDown(pos,l,r);//下推标记，否则sum可能不正确 if(L<=l && R>=r)//节点区间在操作区间之内，直接返回 { return sum[pos]; } //统计答案 long long ans=0; if(L<=mid) ans+=Query(lson[pos],l,mid,L,R); if(R>mid) ans+=Query(rson[pos],mid+1,r,L,R); PushUp(pos); return ans;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { int tmp; cin>>tmp; UpZone(root,1,n,i,i,tmp); } for(int j=1;j<=m;j++) { int a,b,c,d; cin>>a; if(a==1) { cin>>b>>c>>d; UpZone(root,1,n,b,c,d); } else { cin>>b>>c; cout<
            
             <