To the moon
1. 标记不下传，对修改一个区间，在路径上都加上这个标记影响，当 l <= x && y <= r 时可直接返回。
2. 树的空间至少开到 N * 24.

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
struct node {
    int lc, rc, add;
    long long dat;
} t[N * 25];
int n, m, tot, T;
int root[N];

int build(int l, int r) {
    int p = ++ tot;
    if(l == r) {
        cin >> t[p].dat;
        return p;
    }
    int mid = l + r >> 1;
    t[p].lc = build(l, mid);
    t[p].rc = build(mid + 1, r);
    t[p].dat = t[t[p].lc].dat + t[t[p].rc].dat;
    return p;
}

int insert(int now, int l, int r, int x, int y, int val) {
    int p = ++tot;
    t[p] = t[now];
    t[p].dat = t[now].dat + (long long)val * (min(r, y) - max(l, x) + 1);
    if(x <= l && r <= y) {
        t[p].add += val;
        return p;
    }
    int mid = l + r >> 1;
    if(x <= mid) t[p].lc = insert(t[now].lc, l, mid, x, y, val);
    if(y > mid) t[p].rc = insert(t[now].rc, mid + 1, r, x, y, val);
    return p;
}

long long ask(int now, int l, int r, int x, int y) {
    if(x <= l && r <= y) return t[now].dat;
    int mid = l + r >> 1;
    long long ans = (long long)t[now].add * (min(r, y) - max(l, x) + 1);
    if(x <= mid) ans += ask(t[now].lc, l, mid, x ,y);
    if(y > mid) ans += ask(t[now].rc, mid + 1, r, x, y);
    return ans;
}

int main() {
    while(cin >> n >> m) {
        memset(t, 0, sizeof(t));
        memset(root, 0, sizeof(root));
        tot = 0;
        root[T = 0] = build(1, n);
        for(int i = 1; i <= m; i++) {
            char ch;
            cin >> ch;
            if(ch == 'C') {
                int l, r, d;
                cin >> l >> r >> d;
                root[++T] = insert(root[T - 1], 1, n, l, r, d);
            }
            if(ch == 'Q') {
                int l, r;
                cin >> l >> r;
                cout << ask(root[T], 1, n, l, r) << endl;
            }
            if(ch == 'H') {
                int l, r, t;
                cin >> l >> r >> t;
                cout << ask(root[t], 1, n, l, r) << endl;
            }
            if(ch == 'B') cin >> T;
        }
    }
    return 0;
}