线段树（区间修改）-白红宇

线段树（区间修改）

阅读量：4693 次

发布时间：2019-06-09

本文共 2035 字，大约阅读时间需要 6 分钟。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;#define ll long longinline int read() { int x = 0,ff = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * ff;}inline void write(ll x) { if(x < 0) putchar('-'),x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0');}const int INF = 0x3f3f3f3f;const int MAXN = 5e5 + 100;const int MAXM = 3e3 + 10;int n,m,a[MAXN];struct Tree { int left,right; ll sum,add; #define l(x) t[x].left #define r(x) t[x].right #define sum(x) t[x].sum #define add(x) t[x].add}t[MAXN];void build(int p,int l,int r) { l(p) = l; r(p) = r; if(l == r) {sum(p) = a[l]; return ; } int mid = (l + r) / 2; build(p * 2,l,mid); build(p * 2 + 1,mid + 1,r); sum(p) = sum(p * 2) + sum(p * 2 + 1);}void spread(int p) { if(add(p)) { sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1); sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1); add(p * 2) += add(p); add(p * 2 + 1) += add(p); add(p) = 0; }}void change(int p,int l,int r,int d) { if(l <= l(p) && r >= r(p)) { sum(p) += (ll) d * (r(p) - l(p) + 1); add(p) += d; return ; } spread(p); int mid = (l(p) + r(p)) / 2; if(l <= mid) change(p * 2,l,r,d); if(r > mid) change(p * 2 + 1,l,r,d); sum(p) = sum(p * 2) + sum(p * 2 + 1);}ll ask(int p,int l,int r) { if(l <= l(p) && r >= r(p)) return sum(p); spread(p); int mid = (l(p) + r(p)) / 2; ll val = 0; if(l <= mid) val += ask(p * 2,l,r); if(r > mid) val += ask(p * 2 + 1,l,r); return val;}int main() { n = read(); m = read(); for(int i = 1; i <= n; ++i) a[i] = read(); build(1,1,n); for(int i = 1; i <= m; ++i) { char op; int l,r,d; cin >> op; l = read(); r = read(); if(op == 'C') { d = read(); change(1,l,r,d); } else { write(ask(1,l,r)); putchar('\n'); } } return 0;}