acwing模板线段树

以下是acwing模板线段树的示例代码：

const int N = 100010;

int n, m;
int a[N];
struct Node {
    int l, r;
    int v, lazy;
} tree[N * 4];

void pushup(int x) {
    tree[x].v = tree[x * 2].v + tree[x * 2 + 1].v;
}

void pushdown(int x) {
    if (tree[x].lazy) {
        int l = tree[x].l, r = tree[x].r;
        int mid = (l + r) >> 1;
        tree[x * 2].v += tree[x].lazy * (mid - l + 1);
        tree[x * 2 + 1].v += tree[x].lazy * (r - mid);
        tree[x * 2].lazy += tree[x].lazy;
        tree[x * 2 + 1].lazy += tree[x].lazy;
        tree[x].lazy = 0;
    }
}

void build(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    if (l == r) {
        tree[x].v = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(x * 2 l, mid);
    build(x * 2 + 1, mid +1, r);
    pushup(x);
}

void modify(int x, int l, int r, int val) {
    if (tree[x].l >= l && tree[x].r <= r) {
        tree[x].v += val * (tree[x].r - tree[x].l + 1);
        tree[x].lazy += val;
        return;
    }
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) >> 1;
    if (l <= mid) modify(x * 2, l, r, val);
    if (r > mid) modify(x * 2 + 1, l, r, val);
    pushup(x);
}

int query(int x, int l, int r) {
    if (tree[x].l >= l && tree[x].r <= r) {
        return tree[x].v;
    }
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) >> 1;
    int sum = 0;
    if (l <= mid) sum += query(x * 2, l, r);
    if (r > mid) sum += query(x * 2 + 1, l, r);
    return sum;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    while (m--) {
        int op, l, r, val;
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> val;
            modify(1, l, r, val);
        } else if (op == 2) {
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}