线段树

#include <iostream>
#include <stdio.h>
#define N 100005
using namespace std;
typedef long long ll;
int q;

class SegmentTree {
protected:
    int n;
    ll a[N],sum[N << 2],lazy[N << 2];
    void pushup(int pos) {
        sum[pos] = sum[pos << 1] + sum[pos << 1 | 1];
    }
    void pushdown(int pos,int s,int mid,int t) {
        if(lazy[pos]) {
            sum[pos << 1] += lazy[pos] * (mid-s+1);
            sum[pos << 1 | 1] += lazy[pos] * (t - mid);
            lazy[pos << 1] += lazy[pos];
            lazy[pos << 1 | 1] += lazy[pos];
            lazy[pos] = 0;
        }
    }
public:
    void init() {
        scanf("%d%d",&n,&q);
        for(int i = 1; i<=n; i++)
            scanf("%lld",&a[i]);
        build(1,n,1);
    }
    void build(int l,int r,int pos) {
        if(l == r) {
            sum[pos] = a[l];
            return ;
        }
        ll mid = l + r >> 1;
        build(l, mid, pos << 1);
        build(mid + 1,r, pos << 1 | 1);
        pushup(pos);
    }
    void update(int l,int r,ll c,int s,int t,ll pos) {
        if(l <= s && t <= r) {
            sum[pos] += (t - s + 1) * c;
            lazy[pos] += c;
            return ;
        }
        ll mid = (s+t) >> 1;
        pushdown(pos,s,mid,t);
        if(l <= mid) update(l,r,c,s,mid,pos << 1);
        if(r > mid)  update(l,r,c,mid+1,t,pos << 1 | 1);
        pushup(pos);
    }
    ll getsum(ll l,ll r,ll s,ll t,ll pos) {
        if(l <= s && t <= r) return sum[pos];
        ll mid = (s+t)>>1;
        pushdown(pos,s,mid,t);
        ll ans = 0;
        if(l <= mid) ans += getsum(l,r,s,mid,pos << 1);
        if(r > mid)  ans += getsum(l,r,mid+1,t,pos << 1 | 1);
        return ans;
    }
    int getN() { return n; }
} s;

int main() {
    s.init();
    while(q--) {
        getchar();
        char op; scanf("%ch",&op);
        int x,y; scanf("%d%d",&x,&y);
        if(op == 'C') {
            ll k; scanf("%lld",&k);
            s.update(x,y,k,1,s.getN(),1);
        } else {
            printf("%lld\n",s.getsum(x,y,1,s.getN(),1));
        }
    }
    return 0;
}