python/TangDou/AcWing/SegmentTree/ZKW/P3372_5.cpp

#include <iostream>
using namespace std;

typedef long long LL;
#define ls u << 1
#define rs u << 1 | 1
const int N = 100010;

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int n, q;
struct Node {
    int l, r;
    LL sum, tag; //区间总和，修改的数值（懒标记）
} tr[N << 2];

//更新统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

//父节点向子孙节点传递信息
void pushdown(int u) {
    if (tr[u].tag) {
        //更新儿子的tag信息，是为了更下一层的数据传递
        // tag传递到子段，节段的sum和需要按 区间长度*root.tag 进行增加
        tr[ls].tag += tr[u].tag;
        tr[ls].sum += LL(tr[ls].r - tr[ls].l + 1) * tr[u].tag;
        tr[rs].tag += tr[u].tag;
        tr[rs].sum += LL(tr[rs].r - tr[rs].l + 1) * tr[u].tag;
        //别忘了清除懒标记
        tr[u].tag = 0;
    }
}

//构建
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r; //标记范围
    if (l == r) {             //叶子
        tr[u].sum = read();   //区间内只有一个元素l(r),区间和为read(),不需要记录向下的传递tag
        return;
    }

    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r); //左右儿子构建
    pushup(u);                                //通过左右儿子构建后，向祖先节点反馈统计信息变化
}

//以u为根，在区间[l,r]之间全都增加d
void add(int u, int l, int r, int d) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += LL(tr[u].r - tr[u].l + 1) * d; //总和增加
        tr[u].tag += d;                             //懒标记+d
        return;
    }
    pushdown(u); // 如果自己身上有旧的tag数值，在递归前需要将原tag值pushdown到子孙节点去
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) add(ls, l, r, d); //与左区间有交集
    if (r > mid) add(rs, l, r, d);  //与右区间有交集
    pushup(u);                      //将结果的变更更新到祖先节点
}

//关键的查询操作
LL query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    /*懒标记的思想：在更新时只标识不修改，有查询时现用现改的思想。这么做的目的当然是怕有多组修改，
    就需要修改多次,而且路径太长不划算。如果只标识不修改，直接返回，当然快了。比如修改了3次后查询一次，
    也只是真正修改了一次，降低了修改次数。
    */
    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if (l <= mid) res = query(ls, l, r);
    if (r > mid) res += query(rs, l, r);
    //左查+ 右查 = 总和
    return res;
}

int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("P3372.in", "r", stdin);
#endif
    n = read(), q = read();

    //构建线段树
    build(1, 1, n);

    while (q--) {
        int a, b, c, d;
        a = read(), b = read(), c = read();
        if (b > c) swap(b, c);
        if (a == 1)
            d = read(), add(1, b, c, d);
        else
            printf("%lld\n", query(1, b, c));
    }
    return 0;
}