c++ 线段树模板

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N], d[N << 2], b[N << 2];
int n, q;
inline void build(int l, int r, int p) {
    if (l == r) {
        d[p] = a[l];    //叶子节点
        return ;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, p << 1);  //左子树
    build(mid+1, r, (p << 1) | 1);  //右子树
    d[p] = d[p << 1] + d[(p << 1) | 1]; //深搜回溯记录
}
inline int getsum(int l, int r, int s, int t, int p) {   //区间查询
    if (l <= s && t <= r) {
        return d[p];        //如果区间[s,t]包含在[l,r]之中，返回区间和
    }
    int mid = s + ((t - s) >> 1);
    if (b[p]) {  //如果已经有懒惰标记
        d[p << 1] += b[p] * (mid - s + 1);  //标记下放
        d[(p << 1) | 1] += b[p] * (t - mid);
        b[p << 1] += b[p];      //把标记传给子节点
        b[(p << 1) | 1] += b[p];
        b[p] = 0;   //清空标记
    }
    int sum = 0;
    if (l <= mid) {
        sum = getsum(l, r, s, mid, p << 1);
    }
    if (r > mid) {
        sum += getsum(l, r, mid + 1, t, (p << 1) | 1);
    }
    return sum;
}
inline void update(int l, int r, int c, int s, int t, int p) {
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c;
        b[p] += c;  //标记(lazy)
        return ;
    }
    int mid = s + ((t - s) >> 1);
    if (b[p]) {     //如果有标记
        d[p << 1] += b[p] * (mid - s + 1);  //标记下放
        d[(p << 1) | 1] += b[p] * (t - mid);
        b[p << 1] += b[p];      //把标记传给子节点
        b[(p << 1) | 1] += b[p];
        b[p] = 0;   //清空标记
    }
    if (l <= mid) {
        update(l, r, c, s, mid, p << 1);  //更新左节点
    }
    if (r > mid) {
        update(l, r, c, mid + 1, t, (p << 1) | 1);
    } d[p] = d[p << 1] + d[(p << 1) | 1];   //计算节点区间和
}
signed main() {
    scanf("%lld%lld", &n, &q);
    for (int i = 1;i <= n;i++) {
        scanf("%lld", &a[i]);
    }
    build(1, n, 1);
    while (q--) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        if (u == 2) { 
            printf("%lld\n", getsum(v, w, 1, n, 1));
        } else {
            int o;
            scanf("%lld", &o);
            update(v, w, o, 1, n, 1);       //区间和
        }
    }
    return 0;
}