线段树

代码思路

主体部分：

初始化，修改，查询
（即build，update，query三个函数）

辅助部分：

区间值维护，打懒标记，消懒标记
（即push_up，add_tag，push_down三个函数）

简化部分：

自定义数据类型，左右儿子自助计算
（struct Tree，ls&rs函数）

原理（极简）

树+分块=线段树，无尽的二分

代码注释

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// 区间修改，区间查询，区间和 
const int N = 4e6+5; // 数据范围，建议x4，多开不上当，多开不吃亏
ll a[N], tree[N], tag[N];

int ls(int p){return p << 1;} // 左儿子
int rs(int p){return p<<1|1;} // 右儿子

void push_up(int p){
    tree[p] = tree[ls(p)] + tree[rs(p)];
} // 维护区间值（运算可根据题意变动，如求最大值等）

void build(int p, int pl, int pr){ // 初始化
    tag[p] = 0; // 懒运算标记（lazy_tag）
    if(pl == pr){tree[p] = a[pl]; return ;}
    // 若已经走到了最底层，则根据原数列赋值
    int mid = (pl+pr)>>1; // 将当前区间“平均地”分为两块
    build(ls(p), pl, mid); // 左
    build(rs(p), mid+1, pr); // 右
    push_up(p); // 计算区间值
}

void add_tag(int p, int pl, int pr, ll d){
    tag[p] += d; // 更新懒运算标记（add_lazy_tag）
    tree[p] += d*(pr-pl+1); // 更新区间值，记得要算区间内所有数的变动
}

void push_down(int p, int pl, int pr){ // 把懒标记转移到子树
    if(!tag[p]) return ;
    int mid = (pl+pr)>>1; // 一分为二（梅开二度）
    add_tag(ls(p), pl, mid, tag[p]); // 左
    add_tag(rs(p), mid+1, pr, tag[p]); // 右
    tag[p] = 0; // 消除标记
}

void update(int l, int r, int p, int pl, int pr, ll d){ // 区间修改（[l,r]+d）
    if(l <= pl && r >= pr){ // 如果被完全覆盖
        add_tag(p, pl, pr, d); // 打上懒标记（等到之后不能完全覆盖的时候用）
        return ; // 不用跑子树
    }
    push_down(p, pl, pr); // 不能完全覆盖：先把懒标记传下去（懒标记一定是完全覆盖的）
    int mid = (pl+pr)>>1; // 一分为二（梅花三弄）
    if(l <= mid) update(l, r, ls(p), pl, mid, d); // 如果左边被（部分）覆盖
    if(r > mid) update(l, r, rs(p), mid+1, pr, d); // 如果右边被（部分）覆盖
    push_up(p); // 子树已经更新完，用儿子的值维护当前区间值
}

ll query(int l, int r, int p, int pl, int pr){ // 区间查询（[l,r]）
    if(l <= pl && r >= pr) return tree[p]; // 如果被完全覆盖：返回区间值
    push_down(p, pl, pr); // 不能完全覆盖，：为了保证值是最新的，传递懒标记
    ll ret = 0; // 返回值：统计左、右区间被覆盖部分合并后的值
    int mid = (pl+pr)>>1; // 一分为二（大四喜）
    if(l <= mid) ret += query(l, r, ls(p), pl, mid); // 如果左边被（部分）覆盖
    if(r > mid) ret += query(l, r, rs(p), mid+1, pr); // 如果右边被（部分）覆盖
    return ret; // 返回答案
}

int main(){
    int n, m; // 原数列长为n，对其有m次操作
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]); // 输入原数列

    build(1, 1, n); // 建树（根节点编号为1,代表了[1,n]的区间范围）

    for(int i = 1; i <= m; i++){
        int type, l, r; ll d;
        scanf("%d", &type); // 操作类别
        if(type == 1){ // type[1]:修改区间[l,r]中的数，使其值加d
            scanf("%d%d%lld", &l, &r, &d);
            update(l, r, 1, 1, n, d);
        }
        if(type == 2){ // type[2]：输出区间[l,r]的区间和
            scanf("%d%d", &l, &r);
            printf("%lld\n", query(l, r, 1, 1, n));
        }
    }
    return 0;
}