原文章（线段树）

0x01 种一颗线段树

假如我现在有一个数组A，总共有n个元素，我既想实现区间修改，又想单个修改，这时候种一颗线段树来维护这个数组，能平衡收益。

0x02 怎么建立？

线段树是一颗平衡二叉树，双亲结点是区间的和，左右子节点是双亲区间分两半的区间

image-20240224211506204

每个节点 p 的左右子节点的编号分别为 2p 和 2p+1，假设 双亲结点p 的为区间 [l , r]的和。

设 mid = [(l + r)/2]，那么两个子节点分别存储[l , mid] 和 [mid+1 , r]的和。可以发现，左节点对应的区间长度，与右节点相同或者比之恰好多1。

知道这些后，便可以用递归的方法来种一颗线段树了。大体的思想就是，从叶子结点开始，从下往上逐步建立。这便是递归的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void build(elem l = 1, elem r = n, elem p = 1){
	// 到达叶子节点
    if (l == r){ 
    	// 到达叶子节点
        tree[p] = A[l];
        // 用数组中的数据赋值
    }
    else{
        elem mid = (l + r) / 2;
        build(l, mid, p * 2); 
        // 先建立左右子节点
        build(mid + 1, r, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1]; 
        // 该节点的值等于左右子节点之和
    }
}

0x03 修改维护

在讲区间修改前，要先引入一个 “懒标记”（lazy） 的概念。懒标记是线段树的精髓所在。对于区间修改，朴素的想法是用递归的方式一层层修改（类似于线段树的建立），但这样的时间复杂度比较高。使用懒标记后，对于那些正好是线段树节点的区间，我们不继续递归下去，而是打上一个标记，将来要用到它的子区间的时候，再向下传递。

给目标区间[l , r]加上数d。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void update(ll l, ll r, ll d, ll p = 1, ll cl = 1, ll cr = n)
{
    if (cl > r || cr < l) // 区间无交集
        return; // 剪枝
    else if (cl >= l && cr <= r) // 当前节点对应的区间包含在目标区间中
    {
        tree[p] += (cr - cl + 1) * d; // 更新当前区间的值
        if (cr > cl) // 如果不是叶子节点
            mark[p] += d; // 给当前区间打上标记
    }
    else // 与目标区间有交集，但不包含于其中
    {
        ll mid = (cl + cr) / 2;
        mark[p * 2] += mark[p]; // 标记向下传递
        mark[p * 2 + 1] += mark[p];
        tree[p * 2] += mark[p] * (mid - cl + 1); // 往下更新一层
        tree[p * 2 + 1] += mark[p] * (cr - mid);
        mark[p] = 0; // 清除标记
        update(l, r, d, p * 2, cl, mid); // 递归地往下寻找
        update(l, r, d, p * 2 + 1, mid + 1, cr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 根据子节点更新当前节点的值
    }
}

分三种情况处理，当前结点p的区间[cl , rl]，与目标区间无交集，包含关系，有交集。

用懒标记来给维护区间的加减

0x04 区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll query(ll l, ll r, ll p = 1, ll cl = 1, ll cr = n)
{
    if (cl > r || cr < l)
        return 0;
    else if (cl >= l && cr <= r)
        return tree[p];
    else
    {
        ll mid = (cl + cr) / 2;
        push_down(p, cr - cl + 1);
        return query(l, r, p * 2, cl, mid) + query(l, r, p * 2 + 1, mid + 1, cr); 
        // 上一行拆成三行写就和区间修改格式一致了
    }
}