线段树(lazy标记)

  1 # include<cstdio>
  2 # include<iostream>
  3 
  4 using namespace std;
  5 
  6 # define MAX 100004
  7 # define lid id<<1
  8 # define rid id<<1|1
  9 
 10 typedef long long LL;
 11 int n;
 12 
 13 struct Segtree
 14 {
 15     int l,r;
 16     LL lazy,sum;
 17     inline int len()
 18     {
 19         return r-l+1;
 20     }
 21 }tree[MAX*4];
 22 
 23 int a[MAX];
 24 
 25 void push_up( int id )
 26 {
 27     tree[id].sum = tree[rid].sum+tree[lid].sum;
 28 }
 29 
 30 void push_down( int id )
 31 {
 32     if ( tree[id].lazy==0 )
 33         return;
 34     tree[lid].lazy += tree[id].lazy;
 35     tree[rid].lazy += tree[id].lazy;
 36     tree[lid].sum += tree[id].lazy*tree[lid].len();
 37     tree[rid].sum += tree[id].lazy*tree[rid].len();
 38     tree[id].lazy = 0;
 39 }
 40 
 41 void build( int id,int l,int r )
 42 {
 43     tree[id].l = l; tree[id].r = r;
 44     if ( l==r )
 45     {
 46         tree[id].sum = a[l];
 47         return;
 48     }
 49     int mid = (tree[id].l+tree[id].r)/2;
 50     build(lid,l,mid);
 51     build(rid,mid+1,r);
 52     push_up(id);
 53 }
 54 
 55 void update( int id,int l,int r,int val )
 56 {
 57     if ( tree[id].l==l&&tree[id].r==r )
 58     {
 59         tree[id].lazy += val;
 60         tree[id].sum += 1LL*val*tree[id].len();
 61         return;
 62     }
 63     push_down(id);
 64     int mid = ( tree[id].l+tree[id].r )/2;
 65     if ( r <= mid )
 66         update(lid,l,r,val);
 67     else if ( l > mid )
 68         update(rid,l,r,val);
 69     else
 70     {
 71         update(lid,l,mid,val);
 72         update(rid,mid+1,r,val);
 73     }
 74     push_up(id);
 75 }
 76 
 77 LL query( int id,int l,int r )
 78 {
 79     if ( tree[id].l==l&&tree[id].r==r )
 80     {
 81         return tree[id].sum;
 82     }
 83     push_down(id);
 84     int mid = ( tree[id].l+tree[id].r )/2;
 85     if ( r <= mid )
 86         return query(lid,l,r);
 87     else if ( l > mid )
 88         return query(rid,l,r);
 89     else
 90         return query(lid,l,mid)+query(rid,mid+1,r);
 91 }
 92 
 93 int main(void)
 94 {
 95     while ( scanf("%d",&n)!=EOF )
 96     {
 97         for ( int i = 1;i <= n;i++ )
 98         {
 99             scanf("%d",&a[i]);
100         }
101         build(1,1,n);
102         int q; scanf("%d",&q);
103         while( q-- )
104         {
105             int ll,rr,t3; scanf("%d%d%d",&ll,&rr,&t3);
106             update(1,ll,rr,t3);
107             LL ans = query(1,ll,rr);
108             printf("%lld
",ans);
109         }
110     }
111 
112     return 0;
113 }