acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

4
55
9
15

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
struct Node{ 
   
    int l,r;
    ll v;
    ll add;    //懒惰标记,保存当前节点以及子节点应该加上的值
}tr[N * 4];
int a[N];
void push_up(int u){ 
   
    tr[u].v = tr[left(u)].v + (tr[left(u)].r - tr[left(u)].l + 1) * tr[left(u)].add
     + tr[right(u)].v + (tr[right(u)].r - tr[right(u)].l + 1) * tr[right(u)].add;
}
void push_down(int u){ 
   
    if(tr[u].add){ 
   
        tr[u].v += (tr[u].r - tr[u].l + 1) * tr[u].add;
        tr[left(u)].add += tr[u].add;
        tr[right(u)].add += tr[u].add;
        tr[u].add = 0;
    }
}
void build(int l,int r,int u){ 
   
    if(l == r){ 
   
        tr[u] = { 
   l,r,a[l],0};
        return;
    }
    else{ 
   
        tr[u] = { 
   l,r,0,0};
        int mid = (l + r) >> 1;
        build(l, mid, left(u));
        build(mid + 1, r, right(u));
        push_up(u);
    }
}
ll query(int l,int r,int u){ 
   
    push_down(u);
    if(tr[u].l >= l && tr[u].r <= r){ 
   
        return tr[u].v;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll sum = 0;
    if(l <= mid)sum += query(l,r,left(u));
    if(r > mid)sum += query(l,r,right(u));
    return sum;
}
void modify(int l,int r,int x,int u){ 
   
    if(tr[u].l >= l && tr[u].r <= r)tr[u].add += x;
    else{ 
   
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid)modify(l,r,x,left(u));
        if(r > mid)modify(l,r,x,right(u));
        push_up(u);     //修改了值就要push_up
    }
}
void update(int x,int y,int u){ 
   
    if(tr[u].l == x && tr[u].r == x)tr[u].v = y;
    else{ 
   
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid)update(x,y,left(u));
        else update(x,y,right(u));
        push_up(u);
    }
}
int main(){ 
   
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n;i ++){ 
   
        cin>>a[i];
    }
    build(1,n,1);
    char c;
    int l,r,a;
    for(int i = 0;i < m;i ++){ 
   
        cin>>c>>l>>r;
        if(c == 'Q'){ 
   
            cout<<query(l,r,1)<<endl;
        }else if(c == 'C'){ 
   
            cin>>a;
            modify(l,r,a,1);
        }
    }
    return 0;
}