线段树

#include <cstdio>
#define int long long
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const ll N = 109000;
int a[N];
struct segment_tree{ 
    struct node {
        int l, r;
        int L, R;
        int lazy;
        int data;
    }tr[N << 2];
    inline void pushup(int p) {
        if (tr[tr[p].l].lazy) {
            pushdown(tr[p].l);
        }
        if (tr[tr[p].r].lazy) {
            pushdown(tr[p].r);
        }
        tr[p].data = tr[tr[p].l].data  +  tr[tr[p].r].data /*+ (tr[tr[p].l].R - tr[tr[p].l].L + 1 ) * tr[tr[p].l].lazy + (tr[tr[p].r].R - tr[tr[p].r].L + 1) * tr[tr[p].r].lazy*/; }
    inline void pushdown(int p) {tr[tr[p].l].lazy += tr[p].lazy;tr[tr[p].r].lazy += tr[p].lazy;tr[p].data += tr[p].lazy * (tr[p].R - tr[p].L + 1); tr[p].lazy = 0;}
    inline void build(int l, int r, int p) {
        if (l == r) {
            tr[p].L = tr[p].R = l;
            tr[p].data = a[l];return;
        }
        tr[p].l = p * 2;
        tr[p].r = p * 2 + 1;
        tr[p].L = l, tr[p].R = r;
        int mid = l + r >> 1;
        build(l, mid, tr[p].l);
        build(mid + 1, r, tr[p].r);
        pushup(p);
    }
    inline int ask(int l, int r, int p) {
        if (tr[p].L >= l && tr[p].R <= r)return tr[p].data + (tr[p].R - tr[p].L + 1) * tr[p].lazy;
        int ret = 0;
        int mid = tr[p].L + tr[p].R >> 1;
        if (tr[p].lazy) pushdown(p);
        if (tr[tr[p].r].L <= r) ret += ask(l, r, tr[p].r);
        if (tr[tr[p].l].R >= l) ret += ask(l, r, tr[p].l);
        return ret;
    }
    inline void add(int l, int r, int p, int ad) {
        if (tr[p].L >= l && tr[p].R <= r) {
            tr[p].lazy += ad;
            return;
        }
        if (tr[tr[p].r].L <= r)  add(l, r, tr[p].r ,ad);
        if (tr[tr[p].l].R >= l ) add(l, r, tr[p].l, ad);
        pushup(p);
    }
}T;

signed main() {
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    T.build(1, n, 1);
    while (m--) {
        int op;scanf("%lld", &op);
        if (op == 1 ) {
            int x, y, k;
            scanf("%lld%lld%lld", &x, &y, &k);
            T.add(x, y, 1, k);
        } else {
            int x, y;
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", T.ask(x, y, 1));
        }
    }
}

线段树

原文：https://www.cnblogs.com/Xiao-yan/p/14684776.html