线段树（区间修改）

原理

见《进阶指南》第216页。

模板题

洛谷-P3372-【模板】线段树 1

#include <iostream>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 100010;
struct segmentTreeNode { // [l, r]
    int l, r;
    LL data;
    int add;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define data(x) t[x].data
    #define add(x) t[x].add
};
LL a[N];
segmentTreeNode t[N << 2];

void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        data(rt) = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    data(rt) = data(ls) + data(rs);
}
void spread (int rt) {
    if (add(rt) != 0) {
        data(ls) += add(rt) * (r(ls) - l(ls) + 1);
        data(rs) += add(rt) * (r(rs) - l(rs) + 1);

        add(ls) += add(rt);
        add(rs) += add(rt);
        add(rt) = 0;
    }
}
void modify (int rt, int l, int r, int val) { // [l, r] += val
    if (l <= l(rt) && r(rt) <= r) {
        data(rt) += (LL)val * (r(rt) - l(rt) + 1);
        add(rt) += val;
        return;
    }
    spread(rt);
    int mid = l(rt) + r(rt) >> 1;
    if (l <= mid) modify(ls, l, r, val);
    if (r >= mid + 1) modify(rs, l, r, val);
    data(rt) = data(ls) + data(rs);
}
LL query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    spread(rt);
    int mid = l(rt) + r(rt) >> 1;
    LL res = 0;
    if (l <= mid) res += query(ls, l, r);
    if (r >= mid + 1) res += query(rs, l, r);
    return res;
}

int main () {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);

    build(1, 1, n);
    for (int i = 1, opt; i <= m; ++ i) {
        scanf("%d", &opt);
        if (opt == 1) {
            int l, r, val;
            scanf("%d%d%d", &l, &r, &val);
            modify(1, l, r, val);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}