题目如下：

poj 3468

输入整数n，q，然后输入n个数的序列，再然后输入q条询问，询问有两种类型：

Q  l   r   代表打印出区间【l，r】的和

C  l    r    v   代表区间【l，r】区间的数都加v

基本思路：

这里选择线段树，主要是为了练习线段树标记永久化

下面介绍线段树标记永久化：

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int maxn = 100000+10;ll sum[maxn<<2],add[maxn<<2],arr[maxn];int n,q;void build(int l,int r,int rt){ if(l==r){ sum[rt]=arr[l]; return; } int mid=(l+r)/2; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void update(int L,int R,int val,int l,int r,int rt){ sum[rt]+=(ll)val*(R-L+1); if(l==L&&R==r){ add[rt]+=val; return; } int mid=(l+r)/2; if(R<=mid){ update(L,R,val,l,mid,rt<<1); }else{ if(L>mid){ update(L,R,val,mid+1,r,rt<<1|1); }else{ update(L,mid,val,l,mid,rt<<1); update(mid+1,R,val,mid+1,r,rt<<1|1); } }}ll query(int L,int R,ll ad,int l,int r,int rt){ if(L==l&&R==r){ return sum[rt]+ad*(R-L+1); } int mid=(l+r)/2; if(R<=mid){ return query(L,R,ad+add[rt],l,mid,rt<<1); }else if(L>mid){ return query(L,R,ad+add[rt],mid+1,r,rt<<1|1); }else{ ll ans1=query(L,mid,ad+add[rt],l,mid,rt<<1); ll ans2=query(mid+1,R,ad+add[rt],mid+1,r,rt<<1|1); return ans1+ans2; }}int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ scanf("%I64d",&arr[i]); } build(1,n,1); char op[5]; for(int i=1;i<=q;i++){ scanf("%s",op); if(op[0]=='Q'){ int u,v; scanf("%d%d",&u,&v); cout<
           
            <
           
          
         
        
       
      
     

　　

转自：http://www.cnblogs.com/Hallmeow/p/8004676.html

知识点：线段树标记永久化

对于树套树，主席树等使用到线段树的比较复杂的数据结构，如果我们区间修改的话，打标记后pushdownpushdown或者pushuppushup是很费劲的

那么我们能不能不用pushdownpushdown和pushuppushup呢？当然可以啦！这样就用到标记永久化了！

原理就是： 在路过该节点的时候把修改对答案的影响加上，来省去标记下放的过程

实现起来：

线段树的每个节点维护 sumsum 与 addadd 两个标记

修改时：

设区间[xl,xr][xl,xr]全部加vv

当目前询问区间与当前区间完全重合的时候，更新addadd的值，返回。

在一路下来的时候把所有经过的区间（相当于包含询问区间的区间）的sumsum加上此次修改所产生的影响 v∗(xr−xl+1)v∗(xr−xl+1)。

注意完全重合之后就返回了，也就是说下面的部分的影响还没有更新。不要着急

void update(int rt,int l,int r,int v,int xl,int xr){    sum[rt]+=v*(xr-xl+1);    if(l==xl&&r==xr){        add[rt]+=v; return;    }    int mid=(l+r)>>1;    if(xr<=mid)  update(rt<<1,l,mid,v,xl,xr);    else{        if(xl>mid)   update(rt<<1|1,mid+1,r,v,xl,xr);        else update(rt<<1,l,mid,v,xl,mid),update(rt<<1|1,mid+1,r,v,mid+1,xr);    }}

　　

询问时：

由于上面的更新没有对下面产生影响，所以我们需要一路累加addadd，直到目前询问区间与当前区间完全重合的时候，答案为sum+add∗sum+add∗区间长度

注意累加addadd不用累加上完全重合的区间的addadd，因为它已经在修改的时候对sumsum进行更新了

int query(int rt,int ad,int l,int r,int xl,int xr){    if(xl==l&&xr==r){        return sum[rt]+ad*(xr-xl+1);    }      int mid=(l+r)>>1;    if(xr<=mid) return query(rt<<1,ad+add[rt],l,mid,xl,xr);    else{        if(xl>mid) return query(rt<<1|1,ad+add[rt],mid+1,r,xl,xr);        else return query(rt<<1,ad+add[rt],l,mid,xl,mid)+query(rt<<1|1,ad+add[rt],mid+1,r,mid+1,xr);    }}

　　区间修改线段树标记永久化模板

#include
     
      #include
      
       #include
       
        #define pos(i,a,b) for(int i=(a);i<=(b);i++)#define N 201000using namespace std;int n,m;int sum[N*4],add[N*4];int a[N];void build(int l,int r,int rt){    if(l==r){        sum[rt]=a[l];return;    }    int mid=(l+r)>>1;    build(l,mid,rt<<1);    build(mid+1,r,rt<<1|1);    sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void update(int rt,int l,int r,int v,int xl,int xr){    sum[rt]+=v*(xr-xl+1);    if(l==xl&&r==xr){        add[rt]+=v; return;    }    int mid=(l+r)>>1;    if(xr<=mid)  update(rt<<1,l,mid,v,xl,xr);    else{        if(xl>mid)   update(rt<<1|1,mid+1,r,v,xl,xr);        else update(rt<<1,l,mid,v,xl,mid),update(rt<<1|1,mid+1,r,v,mid+1,xr);    }}int query(int rt,int ad,int l,int r,int xl,int xr){    if(xl==l&&xr==r){        return sum[rt]+ad*(xr-xl+1);    }      int mid=(l+r)>>1;    if(xr<=mid) return query(rt<<1,ad+add[rt],l,mid,xl,xr);    else{        if(xl>mid) return query(rt<<1|1,ad+add[rt],mid+1,r,xl,xr);        else return query(rt<<1,ad+add[rt],l,mid,xl,mid)+query(rt<<1|1,ad+add[rt],mid+1,r,mid+1,xr);    }}int main(){    scanf("%d%d",&n,&m);    pos(i,1,n) scanf("%d",&a[i]);    build(1,n,1);    pos(i,1,m){        int opt;scanf("%d",&opt);        int x,y;scanf("%d%d",&x,&y);        if(opt==1){            int k;scanf("%d",&k);            update(1,1,n,k,x,y);        }        else printf("%d\n",query(1,0,1,n,x,y));    }    return 0;}