线段树（$\tt Segment\ Tree$）

最好用的数据结构，没有之一。

他可以以 $\log_2{n}$ 的复杂度处理区间和，区间最值，单点修改，区间修改等操作，也是非常的好用，有一些题目你可以直接上一个线段树，然后以比正解略劣的解法过掉。

思想

维护一棵树，父亲区间被两个儿子平分，直到分到区间只剩下一个元素（叶子）

假如，我们现在有个 $a$ 数组，要使用线段树完成一些问题。

建成线段树就是这样的：

之后，我们只要是进行单点的操作，就可以顺着叶子把一路上的东西都修改掉，而且由于每次一个点只被分成 $2$ 个儿子，树的层数是 $log_2 n$ 复杂度也有保障。

基本结构

想要用数组存储一个上面的线段树，我们首先是要考虑，节点个数。数一数，发现上图一共有 $33$ 个点。经过长达 114514s 的思考，发现刚好是 $2 n - 1$ 。这难道是巧合吗？显然不是。可以给出如下证明：

叶节点数量 非叶子数量 总节点数量 二叉树效果图
1 0 1
2 1 3
3 2 5
4 3 7

由此可得，想要连接 $n$ 个叶子节点，需要 $n - 1$ 个非叶子节点连接，总结点数应该是 $n + (n -1)=2n-1$ 。

但是，为了建一颗树，我们需要动用链表吗？可以，但是会变得十分复杂，一般情况下，我们可以使用 父子两倍，即父亲下标为 $n$ ，左儿子下标为 $2n$ ，右儿子下标为 $2n + 1$ 的表示方法。而这样的一个方式，我们可以想想他所需的数组大小。

线段树是一颗二叉树。
那么由此可知，此二叉树的高度为img,可证img

然后通过等比数列求和 $\cfrac{a_1(1-q^x)}{1-q}$ 求得二叉树的节点个数，具体公式为 $\cfrac{1 \times (1-2^x)}{1-2}$，（x为树的层数，为树的高度+1)

化简可得 $2^{log_2n+1+1}-1$ ,整理之后即为 $4n$（近似计算忽略掉-1)

其实说成人话，最坏情况下一层只有 $2$ 个叶子，这就代表，我们要开四倍空间防止爆，而不是三倍。

* 使用模拟运算方式，可以得出 $n=36$ 的线段树，是可以打爆 $3n$ 空间种最小的，代码证明：

1
2
3
4
5
6
7
8
9
10
11
void Build(int p, int l, int r){
    cout << p << ' ' << l << ' ' << r << endl;
    if(l==r){
        ans = max(ans, p);
        return ;
    }
    int mid=(l+r)/2;
    Build(p*2, l, mid, a);
    Build(p*2+1, mid+1, r, a);
}
// 判断 ans 即可

那么大小定下来了，接下来就好办了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
const int N = 100010;

class SegTree {
    private :
    	struct Node {
            int L, R; // 表示的区间
            int a; // 结点的值， 根据不同需求可以增加和更改名字
        }node[N << 2]; // 四倍空间 
    public :
    	// 被 Zhoumouren 吃掉了
};

建树

其实在上面证明线段树的空间时，便已经写到的一段证明打爆 $3n$ 空间的代码，就是从建树代码改编的。
再次说明，这里用的时父子两倍的方式，一般来讲足够了。

1
2
3
4
5
6
7
8
9
10
11
void Build(int p, int l, int r) {
    node[p].L = l, node[p].R = r;
    if(l == r) {
        node[p].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
	Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    node[p].sum = node[p << 1].sum + node[p << 1 | 1].sum;
}

修改

线段树的迷人之处在于，它是一颗二叉树，层数为 $log_2n$ 这时候，我们只需要自上而下，最后找到需要的区间（单点可以看成是做右端点相同的区间）便返回。这是线段树的核心思想，也是为什么线段树可以做到在及其短的时间内完成区间操作。

先从单点修改看起。单点，一定是线段树的某个叶子节点。我们不是在定义的时候定义了 $L, R$ 吗？现在只需要求出 $mid$ ，判断线段树的点，在哪一边就可以。相对比较简单。

1
2
3
4
5
6
7
8
9
void ModifyPoint(int p, int x, int v) { // 将 x 点修改为 v
    if(node[p].L == node[p].R) { // 因为你在下面的判断中，就可以保证，你走的一定是我们的要找的这一个点的位置。所以找到叶子，一定是我们要找的。
        node[p].sum = v;
        return ; // 完成目标就返回，防止继续往下搜增加复杂度。这也是线段树复杂度不是暴力的原因。
    }
    int mid = (node[p].L + node[p].R) >> 1; // 这就是求出 mid ，因为我们已经在所有的节点中存了线段，就不需要在函数中增加参数了。
    if(x < mid) ModifyPoint(p << 1, x, v); // mid 左边是左子树，右边是右子树，这是在建树的时候就定下来的规矩。
    else ModifyPoint(p << 1 | 1, x, v); // 这也是线段树的一个规则，只往自已要找的地方跑，就可以保证复杂度。
}

另外，这边还给出复杂度的详细证明：

我们知道，所有的区间，都可以表示为，一个前缀减去另外一个前缀（类似前缀和的道理）
所以我们只需要证明前缀复杂度为 $O (log_2n)$ ，任意区间就都是 $O(log_2n)$ 的复杂度（常数舍去）

只要是寻找前缀，由于线段树找到目标就返回的性质，可以保证，线段树的每一层，至多只被作为一次访问终点。（可以自己画图看看，毕竟这里展示位置有限）

如此图，$vis$ 表示已访问过，$done$ 为终点。

这样每一层只作为一次终点，忽略常数，复杂度即为 $O(log_2n)$ 。

那么，单点修改就是这样，区间修改呢？第一个比较好想到的方法是看成多个单点。但是这样显然不行。应为这样相当于你把上图中 $done$ 的子树，也访问了。又变回了暴力复杂度，这是不满足线段树完成任务即返回的原则的。

那么按照这个原则，我们只能修改 $done$ 的节点的值，正确性没有。这时，我们可以设想，在 $done$ 节点倒水，等我们要访问他的子树的时候，水就顺着流下去，知道我们要访问的终点，这样就可以顺便在查询或其他修改操作的时候同时处理掉我们需要的改变值，正确性可以保证。这就是线段树的区间修改操作，这里的水，其实就是传说中的懒惰标记即 $lazy$ 。

这时候，我们就需要修改线段树节点的结构体定义了：

1
2
3
4
struct Node {
    int L, R;
    int sum, lazy; // 一开始懒惰值为 0 ，因为这时还没有修改过任何值。建树时在设置区间 L、R，时顺便清零，代码不再演示。
}node[N << 2];

在上述单点修改代码的基础上，我们可以得出区间修改代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Add(int p, int v) {
    node[p].sum += (node[p].R - node[p].L + 1) * v; // 每一个点都要加，总共加上元素数量乘以值
    node[p].lazy += v; // 更新懒惰值
}
void Update(int p) {
    if(node[p].lazy == 0) return ; // 如果没有水，就不用传递了
    Add(p << 1, node[p].lazy); // 水流到左子树
    Add(p << 1 | 1, node[p].lazy); // 水流到右子树
    node[p].lazy = 0; // 水流完了（这个懒惰值的使命完成了）
}

void ModifyRange(int p, int L, int R, int v) { // 要将 [L, R] 区间的所有元素增加 v
    if(L <= node[p].L && node[p].R <= R) { // 区间被完全包含
        Add(p, v); // 将这个节点增加 v
        return ; // 达成目标即返回
    }
    Update(p); // 如果顺路遇到了水，便让其流下去（懒惰值的传递）    
    int mid = (node[p].L + node[p].R) >> 1;
    if(L <= mid) ModifyRange(p << 1, L, R, v); // 左边有东西，访问
    if(mid < R) ModifyRange(p << 1 | 1, L, R, v); // 右边有东西，访问
}

查询

单点查询想必大家都会了吧，从根向着目标进发就可以了。

而区间查询，思路和区间修改差不多。但是注意，在区间查询的同时，如果有水，照样得流，不然代码搜下去了，下面的值没有改变，正确性就不可以保证了。

如果你已经完全理解上面所讲，不许代码，未完全理解的，这里给出伪代码

1
2
3
4
5
6
7
8
9
10
11
def QueryRange(p, L, R) : 
    if 完全包含 :
        return node[p].sum;
    Update(p) # 懒惰值传递
    mid = (node[p].L + node[p].R) >> 1
    ans = 0 # 总答案，根据需求改变
    if 左边有东西 :
        更新答案
    if 右边有东西 :
        更新答案
    return ans

总结

最后的最后，感谢读完此文。附上线段树大模板（某些人写的太丑了，不如我的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class SegTree{
    private:

    struct Node{
        int l, r;
        long long sum;
        long long lazy;
    }node[N*4];

    public:

    void Add(int p, long long v){
        node[p].sum+=v*(node[p].r-node[p].l+1);
        node[p].lazy+=v;
    }
    void DownAdd(int p){
        if(node[p].lazy==0) return ;
        Add(p*2, node[p].lazy);
        Add(p*2+1, node[p].lazy);
        node[p].lazy=0;
    }
    void Build(int p, int l, int r, int *a){
        node[p].l=l, node[p].r=r, node[p].lazy=0;
        if(l==r){
            node[p].sum=a[l];
            return ;
        }
        int mid=(l+r)>>1;
        Build(p*2, l, mid, a);
        Build(p*2+1, mid+1, r, a);
        node[p].sum=node[p*2].sum+node[p*2+1].sum;
    }
    void ModifyRange(int p, int L, int R, long long v){
        if(L<=node[p].l&&node[p].r<=R){
            Add(p, v);
            return ;
        }
        DownAdd(p);
        int mid=(node[p].l+node[p].r)>>1;
        if(L<=mid) ModifyRange(p*2, L, R, v);
        if(mid<R) ModifyRange(p*2+1, L, R, v);
        node[p].sum=node[p*2].sum+node[p*2+1].sum;
    }
    long long QueryRange(int p, int L, int R){
        if(node[p].r<L||node[p].l>R) return 0;
        if(L<=node[p].l&&node[p].r<=R){
            return node[p].sum;
        }
        DownAdd(p);
        int mid=(node[p].l+node[p].r)>>1;
        long long sum=0;
        if(L<=mid) sum+=QueryRange(p*2, L, R);
        if(mid<R) sum+=QueryRange(p*2+1, L, R);
        return sum;
    }
};