线段树

屯代码
（话说调了一下午的线段树，呵呵呵）
wa的原因：修改的时候累加值不是累加线段的长度*x而是累加实际的长度*x
 1 #include<cstdio>
 2 
 3 struct tree{
 4     int l,r,lch,rch,tage;
 5     long long sum;
 6 }tr[400002]={0};
 7 int n,a[200001],m,q,l,r,cnt,x;
 8 void build(int now,int l,int r){
 9     cnt++;
10     tr[cnt].l=l; tr[cnt].r=r;
11     if (l==r){
12         tr[cnt].sum=a[l];
13         return;
14     } 
15     tr[now].lch=cnt+1;
16     int mid=(l+r)/2;
17     build(cnt+1,l,mid);
18     tr[now].rch=cnt+1;
19     build(cnt+1,mid+1,r);
20     tr[now].sum=tr[tr[now].lch].sum+tr[tr[now].rch].sum;
21 }
22 
23 void insert(int now,int l,int r,int x){
24     if (tr[now].l<=l&&tr[now].r>=r) {
25         tr[now].sum+=x*(r-l+1);
26     }
27     if (tr[now].l==l&&tr[now].r==r) {
28     tr[now].tage+=x;
29     return;
30     }
31     int mid=(tr[now].l+tr[now].r)/2;
32     if (l>mid) insert(tr[now].rch,l,r,x);
33     else if (r<=mid) insert(tr[now].lch,l,r,x);
34     else {
35         insert(tr[now].lch,l,mid,x); 
36         insert(tr[now].rch,mid+1,r,x);
37     }
38 }
39 
40 long long query(int now,int l,int r){
41     tr[tr[now].rch].sum+=tr[now].tage*(tr[tr[now].rch].r-tr[tr[now].rch].l+1);
42     tr[tr[now].lch].sum+=tr[now].tage*(tr[tr[now].lch].r-tr[tr[now].lch].l+1);
43     tr[tr[now].lch].tage+=tr[now].tage;
44     tr[tr[now].rch].tage+=tr[now].tage;
45     tr[now].tage=0;
46     if (tr[now].l==l&&tr[now].r==r) return tr[now].sum;
47     int mid=(tr[now].l+tr[now].r)/2;
48     if (mid+1<=l) return query(tr[now].rch,l,r);
49     else if (r<=mid) return query(tr[now].lch,l,r);
50     else return query(tr[now].lch,l,mid)+query(tr[now].rch,mid+1,r);
51 }
52 
53 
54 int main(){
55     scanf("%d",&n);
56     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
57     build(1,1,n);
58     scanf("%d",&m);
59     for (int i=0;i<m;i++){
60         scanf("%d",&q);
61         if (q==1){
62             scanf("%d%d%d",&l,&r,&x);
63             insert(1,l,r,x);
64         }
65         if (q==2){
66             scanf("%d%d",&l,&r);
67             long long ans=query(1,l,r);
68             printf("%lld
",ans);
69         }
70     }
71 }