前言：对于区间修改和区间查询这样的简单问题，打一大堆线段树确实是不划算，所以学习了区间修改+区间修查询的树状数组。

我们定义 为原数列， ,显然  。

若想要将区间 的数全部 则只需要将 , 即可。

             

             

所以，我们维护一个数组  

在将区间 的数全部 则还需同时将 , 。

结论：

 

例题：CODEVS1082 线段树练习3

 

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,q;long long a[200005],c[3][200005];long long lowbit(long long x){ return x&(-x);}void modify(int x,long long pos,long long v){ for(;pos<=n;pos+=lowbit(pos)) c[x][pos]+=v;}long long query(int x,long long pos){ long long ret=0LL;for(;pos;pos-=lowbit(pos)) ret+=c[x][pos];return ret;}int main(){ int i,j,opt; long long l,r,v,sum1,sum2; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); modify(1,i,a[i]-a[i-1]); modify(2,i,(i-1)*(a[i]-a[i-1])); } scanf("%d",&q); for(i=1;i<=q;i++) { scanf("%d%lld%lld",&opt,&l,&r); if(opt==1) { scanf("%lld",&v); modify(1,l,v);modify(1,r+1,-v); modify(2,l,v*(l-1));modify(2,r+1,-v*r); } else { sum1=(l-1)*query(1,l-1)-query(2,l-1); sum2=r*query(1,r)-query(2,r); printf("%lld\n",sum2-sum1); } } return 0; }