题解 | #A Simple Problem with Integers#

using namespace std;

const int N = 1e6 + 10;
typedef long long ll;

ll w[N];  
int n, q;
struct Node {
    int l, r;
    ll sum, add;
} tr[4 * N]; 

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;  
    if (l == r) {
        tr[u].sum = w[l];  
        tr[u].add = 0;   
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);       
    build(u << 1 | 1, mid + 1, r); 
    pushup(u);
}

void pushdown(int u) {
    Node &root = tr[u];
    Node &left = tr[u << 1];
    Node &right = tr[u << 1 | 1];
    left.add += root.add;
    left.sum += (ll)(left.r - left.l + 1) * root.add;
    right.add += root.add;
    right.sum += (ll)(right.r - right.l + 1) * root.add;
    root.add = 0;
}

void modify(int u, int l, int r, ll d) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, d);    
    if (r > mid) modify(u << 1 | 1, l, r, d);
    pushup(u);  
}
ll query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].sum;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll res = 0;
    if (l <= mid) res += query(u << 1, l, r); 
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &w[i]);
    }
    build(1, 1, n);
    while (q--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            ll x;
            scanf("%lld", &x);
            modify(1, l, r, x); 
        } else {
            printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}