题面

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations.

One type of operation is to add some given number to each number in a given interval.

The other is to ask for the sum of numbers in a given interval.

题解

线段树模板

#include
    
     #include
     
      using namespace std;const int maxn = 100010;typedef long long LL;LL a[maxn];struct node{    int l, r;    LL val, addmark;}sgt[maxn<<2];void build(int p, int l, int r){    sgt[p].l = l, sgt[p].r = r;    if(l == r){        sgt[p].val = a[l];    }else{        int m = (l+r)/2;        build(p*2,l,m);        build(p*2+1,m+1,r);        sgt[p].val = sgt[p*2].val+sgt[p*2+1].val;    }}void pushdown(int p){    if(sgt[p].addmark != 0){        LL t = sgt[p].addmark;        sgt[p].addmark = 0;        sgt[p*2].addmark += t;        sgt[p*2+1].addmark += t;        sgt[p*2].val += (sgt[p*2].r-sgt[p*2].l+1)*t;        sgt[p*2+1].val += (sgt[p*2+1].r-sgt[p*2+1].l+1)*t;    }}void add(int p, int l, int r, LL v){    if(l <= sgt[p].l && sgt[p].r <= r){        sgt[p].val += (sgt[p].r-sgt[p].l+1)*v;        sgt[p].addmark += v;        return ;    }    pushdown(p);    int m = (sgt[p].l+sgt[p].r)/2;    if(l <= m)add(p*2,l,r,v);    if(r > m)add(p*2+1,l,r,v);    sgt[p].val = sgt[p*2].val+sgt[p*2+1].val;}LL query(int p, int l, int r){    if(l <= sgt[p].l && sgt[p].r <= r)return sgt[p].val;    pushdown(p); //pushdown    LL m = (sgt[p].l+sgt[p].r)/2, ans = 0;    if(l <= m)ans += query(p*2,l,r);    if(r > m)ans += query(p*2+1,l,r);    return ans;}int main(){    ios::sync_with_stdio(false);    int n, m;    cin>>n>>m;    for(int i = 1; i <= n; i++)cin>>a[i];    build(1,1,n);    for(int i = 1; i <= m; i++){        char ch;  cin>>ch;        if(ch == 'Q'){            LL x, y;  cin>>x>>y;            cout<
      
       <<"\n";        }else{            LL x, y, z;  cin>>x>>y>>z;            add(1,x,y,z);        }    }    return 0;}
      
     
    

关于线段树2*n空间表示法。

推荐博客