线段树-区间加法模板

  1 /**\
  2 线段树:区间查询 区间修改
  3 input:
  4 5 5
  5 1 5 4 2 3
  6 2 2 4
  7 1 2 3 2
  8 2 3 4
  9 1 1 5 1
 10 2 1 4
 11 output:
 12 11
 13 8
 14 20
 15 \**/
 16 #include 
 17 using namespace std;
 18 #define fi first
 19 #define se second
 20 #define go continue
 21 #define int long long
 22 #define PII pair
 23 #define sf(x) scanf("%lld",&x)
 24 #define ytz int _; sf(_); while(_--)
 25 #define fory(i,a,b) for(int i = a; i <= b; ++i)
 26 #define forl(i,a,b) for(int i = a; i >= b; --i)
 27 #define debug(a) cout << #a << " = " << a < 28 /*---------------------------------------------*/
 29 int n, a[100010];
 30 struct node
 31 {
 32     int l, r, sum, lazy;
 33 };
 34 struct segment_tree
 35 {
 36     node t[100010 * 4];
 37     inline void init_lazy(int root)
 38     {
 39         t[root].lazy = 0;
 40     }
 41     inline void union_lazy(int p, int h)
 42     {
 43         t[h].lazy += t[p].lazy;
 44     }
 45     inline void cal_lazy(int root)
 46     {
 47         t[root].sum += (t[root].r - t[root].l + 1) * t[root].lazy;
 48     }
 49     inline void push_down(int root)
 50     {
 51         if(t[root].lazy != 0)
 52         {
 53             cal_lazy(root);
 54             if(t[root].l != t[root].r)
 55             {
 56                 int ch = root << 1;
 57                 union_lazy(root, ch);
 58                 union_lazy(root, ch + 1);
 59             }
 60             init_lazy(root);
 61         }
 62     }
 63     inline void push_up(int root)
 64     {
 65         int ch = root << 1;
 66         push_down(ch);
 67         push_down(ch + 1);
 68         t[root].sum = t[ch].sum + t[ch + 1].sum;
 69     }
 70     inline void build(int root, int l, int r)
 71     {
 72         t[root].l = l;
 73         t[root].r = r;
 74         init_lazy(root);
 75         if(l != r)
 76         {
 77             int mid = (l + r) >> 1;
 78             int ch = root << 1;
 79             build(ch, l, mid);
 80             build(ch + 1, mid + 1, r);
 81             push_up(root);
 82         }
 83         else
 84         {
 85             t[root].sum = a[l];
 86         }
 87     }
 88     inline void change(int root, int l, int r, int add)
 89     {
 90         push_down(root);
 91         if(t[root].l >= l && t[root].r <= r)
 92         {
 93             t[root].lazy = add;
 94             return;
 95         }
 96         int ch = root << 1;
 97         int mid = (t[root].l + t[root].r) >> 1;
 98         if(r <= mid) change(ch, l, r, add);
 99         else if(l > mid) change(ch + 1, l, r, add);
100         else
101         {
102             change(ch, l, mid, add);
103             change(ch + 1, mid + 1, r, add);
104         }
105         push_up(root);
106     }
107     inline int query(int root, int l, int r)
108     {
109         push_down(root);
110         if(t[root].l >= l && t[root].r <= r)
111         {
112             return t[root].sum;
113         }
114         int ch = root << 1;
115         int mid = (t[root].l + t[root].r) >> 1;
116         if(r <= mid) return query(ch, l, r);
117         else if(l > mid) return query(ch + 1, l, r);
118         else return query(ch, l, mid) + query(ch + 1, mid + 1, r);
119     }
120 } st;
121 int m;
122 signed main()
123 {
124     sf(n), sf(m);
125     fory(i, 1, n) sf(a[i]);
126     st.build(1, 1, n);
127     while(m--)
128     {
129         int op, x, y, z;
130         sf(op);
131         if(op == 1)
132         {
133             sf(x), sf(y), sf(z);
134             st.change(1, x, y, z);
135         }
136 
137         else
138         {
139             sf(x), sf(y);
140             printf("%lld\n", st.query(1, x, y));
141         }
142     }
143     return 0;
144 }