代码

#include <bits/stdc++.h>

using i64 = long long;

const int MaxN = 100005;

i64 a[MaxN];
i64 seg[MaxN << 2];
i64 lazy_add[MaxN << 2];

void pushup(int p) {
    seg[p] = seg[p << 1] + seg[p << 1 | 1];
}

void pushdown(int l, int r, int p) {
    if (lazy_add[p] != 0 && l != r) {
        int mid = (l + r) >> 1;
        seg[p << 1] += lazy_add[p] * (mid - l + 1);
        lazy_add[p << 1] += lazy_add[p];
        seg[p << 1 | 1] += lazy_add[p] * (r - mid);
        lazy_add[p << 1 | 1] += lazy_add[p];
        lazy_add[p] = 0;
    }
    return;
}

void build(int l, int r, int p) {
    if (l == r) {
        seg[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
    pushup(p);
    return;
}

void update(int x, int y, i64 v, int l, int r, int p) {
    if (x <= l && y >= r) {
        seg[p] += v * (r - l + 1);
        lazy_add[p] += v;
        return;
    }
    pushdown(l, r, p);
    int mid = (l + r) >> 1;
    if (x <= mid) update(x, y, v, l, mid, p << 1);
    if (y >= mid + 1) update(x, y, v, mid + 1, r, p << 1 | 1);
    pushup(p);
    return;
}

i64 query(int x, int y, int l, int r, int p) {
    if (x <= l && y >= r) return seg[p];
    pushdown(l, r, p);
    i64 ans = 0;
    int mid = (l + r) >> 1;
    if (x <= mid) ans += query(x, y, l, mid, p << 1);
    if (y >= mid + 1) ans += query(x, y, mid + 1, r, p << 1 | 1);
    return ans;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, n, 1);
    while (m--)
    {
        int op;
        scanf("%d", &op);
        switch (op)
        {
            case 1:
            {
                int x, y;
                i64 k;
                scanf("%d%d%lld", &x, &y, &k);
                update(x, y, k, 1, n, 1);
                break;
            }
            case 2:
            {
                int x, y;
                scanf("%d%d", &x, &y);
                printf("%lld\n", query(x, y, 1, n, 1));
                break;
            }
        }
    }
    return 0;
}

评测结果