线段树 模板

[Draymonders]

单点修改 区间查询

#define lson (rt<<1)
#define rson (rt<<1|1)

const int N = 50000 + 10;

int n;
int s[N];
int tr[N*4];

void build(int rt, int l, int r) {
    if (l == r) {
        tr[rt] = s[l];
        return ;
    }

    int m = (l + r) / 2;
    build(lson, l, m);
    build(rson, m+1, r);
    tr[rt] = tr[lson] + tr[rson];
    return ;
}

void update(int rt, int l, int r, int pos, int val) {
    if (l ==r && l == pos) {
        tr[rt] += val;
        return ;
    }
    int m = (l + r) / 2;
    if (pos <= m) 
        update(lson, l, m, pos, val);
    else
        update(rson, m+1, r, pos, val);
    tr[rt] = tr[lson] + tr[rson];
    return ;
}

// [L,R]为要查询的区间，并且[L, R]是[l, r]的子区间
int query(int rt, int l, int r, int L, int R) {
    if (l == L && r == R) {
        return tr[rt];
    }
    int m = (l + r) / 2;
    if (L > m) {
        return query(rson, m+1, r, L, R);
    } else if (R <= m) {
        return query(lson, l, m, L, R);
    } else {
        return query(lson, l, m, L, m) + query(rson, m+1, r, m+1, R);
    }
}

[Draymonders]

区间更新，区间查询

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (rt<<1)
#define rs (rt<<1|1)
const int N = 1e5 + 10;
ll tr[N * 4];
ll lazy[N * 4];
int n, m;
int mx = 0;

void push_down(int rt, int l, int r) {
    if (lazy[rt] != 0) {
        int m = (l + r) / 2;
        lazy[ls] += lazy[rt];
        lazy[rs] += lazy[rt];
        tr[ls] += lazy[rt] * (m - l + 1);
        tr[rs] += lazy[rt] * (r - m);
        lazy[rt] = 0; 
    }
    return ;
}

void push_up(int rt) {
    tr[rt] = tr[ls] + tr[rs];
    return ;
}

void build(int rt, int l, int r) {
    mx = max(mx, rt);
    if (l == r) {
        lazy[rt] = 0;
        scanf("%d", &tr[rt]);
        return ;
    }
    int m = (l + r) / 2;
    build(ls, l, m);
    build(rs, m+1, r);

    lazy[rt] = 0;
    push_up(rt);
    return ;
}

// 将[L, R]区间加val [L, R]为[l, r]子区间
void update(int rt, int l, int r, int L, int R, ll val) {
    if (l == L && r == R) {
        tr[rt] += val * (r - l + 1);
        lazy[rt] += val;
        return ;
    }
    int m = (l + r) / 2;
    // 懒标记下发
    push_down(rt, l, r);

    if (L > m) {
        update(rs, m+1, r, L, R, val);
    } else if (R <= m) {
        update(ls, l, m, L, R, val);
    } else {
        update(ls, l, m, L, m, val);
        update(rs, m+1, r, m+1, R, val);
    }
    push_up(rt);
}

ll query(int rt, int l, int r, int L, int R) {
    if (l == L && r == R) {
        return tr[rt];
    }
    int m = (l + r) / 2;
    // 懒标记下发
    push_down(rt, l, r);
    if (L > m) {
        return query(rs, m+1, r, L, R);
    } else if (R <= m) {
        return query(ls, l, m, L, R);
    } else {
        return query(ls, l, m, L, m) + query(rs, m+1, r, m+1, R);
    }
}

int main() 
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    while (~scanf("%d%d", &n, &m)) {
        memset(tr, 0, sizeof(tr));
        build(1, 1, n);
        while (m --) {
            int op, x, y;
            scanf("%d %d %d", &op, &x, &y);
            // printf("outputs: %d %d %d\n", op, x, y);
            if (op == 1) {
                ll z;
                scanf("%lld", &z);
                // printf("区间[%d, %d]增加%d\n", x, y, z);
                update(1,1,n,x,y,z);
            } else {
                // printf("查询区间[%d, %d]\n", x, y);
                ll sum = query(1,1,n,x,y);
                printf("%lld\n", sum);
            }
            // puts("tr数组");
            // for (int i=1; i<=mx; i++) {
            //     printf("%lld%c", tr[i], i==mx?'\n':' ');
            // }
            // puts("lazy数组");
            // for (int i=1; i<=mx; i++) {
            //     printf("%d%c", lazy[i], i==mx?'\n':' ');
            // }
        }
    }
    return 0;
}