$$线段树$$

1.线段树的应用：广泛应用于解决在区间上维护信息的问题

支持1.区间求和， 2.区间最值， 3 区间修改，4.区间查询等操作

2.本质：二叉搜索树(也称左右子树)

3.实现思想： 将区间 $[1,n] $ 平均分成2个更小的区间， 直到区间长度为 1(无法再分)

其中$[l,r] $ 存储节点信息，叶节点的长度为 1， 即 $ l == r$。

4.线段树的储存： 堆

父节点编号为 $root$ ，则左儿子编号为 $root * 2$, 右儿子编号 $root * 2 + 1$， 利用二进制优化成 $root << 1$ 和 $root << 1 | 1$，$root << 1$ 即乘以 2， 此时 对应二进制末尾一定是$ 0 $，再$ | 1 $ 末尾一定是 1， 其余位置不变

| 操作：一个为 1 一个为 0 结果为 1

注意：对于一个长度为n的区间， 需要建立大小为4 * n 的数组维护

5. 线段树操作:

• 1.初始化建树： 遍历整棵树即可，左子树 $[l,mid] $， 右子树$[mid+1, r] $
• 2.单点查询： 遍历整棵树， 到达目标节点返回信息
• 3.单点修改： 遍历树， 找到节点就修改
• 4.区间查询： 查询区间 $[x,y]$， 当前遍历到的区间被查询区间包含就返回节点信息；否则，假设当前区间为 $[l, r]$,，中点 $ mid$ ，如果 $x <= mid$ 说明查询区间与&[l,mid]&有交集，返回信息，如果 $y > mid$(右儿子是$[mid + 1, r]$)，说明查询区间与 &[mid + 1, r]&有交集，返回信息； 最后合并即可。
• 5.区间修改： 由于每一次修改一个点的复杂度是线性的，如果每次修改一个点，复杂度退化； 因此引入懒标记：只修改对查询有用的点，没有用的点做好标记，但不会去操作，到要用时再取。

  懒标记使用方法: 遍历到的节点带有懒标记，立即修改当前节点的信息，并且将标记放到左右儿子。

// 线段树基础模板
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 1e6 + 5;

int n, m;
int a[N];
ll sum[N << 2], add[N << 2];
// 线段树数组， 懒标记数组

// 建树
void build(int root, int l, int r){
    if(l == r){sum[root] = a[l]; return;}

    int mid = (l + r) >> 1;
    build(root<<1 , l, mid);
    build(root<<1|1, mid + 1, r);
    sum[root] = sum[root<<1] + sum[root<<1|1];
}

// 记录懒标,， 区间 [x,y] + val <==>  + length([x,y]) * val 
void update(int root, int l, int r, int val){
    add[root] += val; sum[root] += (ll) (r - l + 1) * val;
}

// 下放懒标记的影响
void pushdown(int root, int l, int r){
    if(!add[root]) return;                   // 被懒标记标过就下放懒标记影响
    int mid = (l + r) >> 1;
    update(root<<1, l, mid, add[root]);      // 下放到左区间
    update(root<<1|1, mid+1, r, add[root]);  // 下放到右区间
    add[root] = 0;                           // 懒标记已经使用过,复原,
}

// 区间修改, 插入 root --> 父节点 l,r --> 线段树数组 x,y --> 修改的区间 val --> 修改的值
void insert(int root, int l, int r, int x, int y, int val){
    if(x <= l && r <= y){ update(root, l, r, val); return;} // 打上懒标记

    pushdown(root, l, r);
    int mid = (l + r) >> 1;
    if(x <= mid) insert(root<<1, l, mid, x, y, val);     // 遍历左儿子
    if(y >  mid) insert(root<<1|1, mid+1, r, x, y, val); // 遍历右儿子
    sum[root] = sum[root<<1] + sum[root<<1|1];
}

// 单点修改, 其实就是区间修改的特殊情况 x == y, 一样的, 就不需要在标记懒数组了
// 因为懒数组是为了简化区间修改的复杂度,最终仍然会加到sum, 而单点修改就本身是在改sum
void add_one(int root, int l, int r, int x, int val){
    if(l == r) { sum[root] += val; return;}
    int mid = (l + r) >> 1;
    if(x <= mid) add_one(k<<1, l, mid, x, v);
    else add_one(k<<1|1, mid + 1, r, x, v);
    sum[k] = sum[k<<1|1] + sum[k<<1];
}

// 区间查询
ll query(int root, int l ,int r, int x, int y){
    if(x <= l && r <= y)  return sum[root];   // 区间被包含, 返回答案

    ll res = 0; 
    int mid = (l + r) >> 1;
    pushdown(root, l, r);                                  //下放懒标记的影响
    if(x <= mid) res += query(root<<1, l, mid, x, y);      // 会用到左儿子，下放到左儿子
    if(y > mid)  res += query(root<<1|1, mid+1, r, x, y);  // 右儿子同理
    return res;
}

int main(){
    scanf("%d%d",&n,&m);

    for(int i = 1; i <= n; i++) scanf("%d", a + i);

    build(1, 1, n); // 建树， root 从 1 开始

    while(m--){
        int op, x, y;
        scanf("%d%d%d", &op,&x,&y);

        if(op == 1){
            int val; scanf("%d", &val);
            insert(1, 1, n, x, y, val);
        }
        else  printf("%lld\n", query(1, 1, n, x, y));
    }

    return 0;
}

例题,单点修改

区间修改

作者能力有限欢迎指正！