# 线段树

## 引入

线段树是算法竞赛中常用的用来维护**区间信息**的数据结构。

树状数组可以在 $O(\log n)$ 的时间内实现**单点修改**、**区间查询**（求和、求最值、求异或等）；而线段树还可以在 $O(\log n)$ 时间内实现**区间修改**操作，例如将 $[L, R]$ 区间范围内的值都加上一个常数，乘以一个常数，或者都置为某个数。

## 常规线段树

### 结构

就我的理解而言，常规的线段树能实现的功能其实与树状数组没什么区别，都只能在 $O(\log n)$ 时间内实现**单点修改**和**区间查询**。

线段树的构造：给定一个区间 $[L, R]$，取 $mid = L + (R - L) / 2$，将它划分为 $[L, mid]$ 和 $[mid + 1, R]$ 两个区间，如此递归地划分，直到区间长度为 $1$ 为止，这些父区间和划分为左右两边的子区间，在组织结构上很像二叉树的父结点和子结点，这也就是**线段树**的名字由来。

我们这里以区间求和为例，**线段树**的每个结点对应着相应的线段上的点的和，以数组 $a = \{1,2,3,4,5,6,7,8,9,10\}$ 为例，线段树的结构如图所示：

![wJhuOqtjM5Hyvnx](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-070007.jpg)

可以看到，线段树存储的基础形式是数组，与二叉堆的存储方式一致，假设当前父结点的编号为 $p$，那么左儿子的编号为 $2 * p$，右儿子的编号为 $2 * p + 1$，结点的值为对应区间的和。

构建线段树的方式其实与“求以该节点为根节点的子树的和”类似，递归处理是很容易的。

代码实现：

```cpp
void Build(int idx, int l, int r, vector<int> &nums) {
    if (l == r) {
        seg[idx] = nums[l];
        return;
    }
    int mid = l + (r - l) / 2;
    Build(2 * idx, l, mid, nums); // 递归构建左子树
    Build(2 * idx, mid + 1, r, nums); // 递归构建右子树
    seg[idx] = seg[2 * idx] + seg[2 * idx + 1]; // 更新 seg[idx]
}
```


### 区间查询

线段树的区间查询，其实只要掌握了递归，就很好理解了。

我们也是对线段树一层一层地往下查询，先比较待查询区间是否能完全覆盖当前线段树区间，如果能完全覆盖，则返回当前区间的值；否则继续比较待查询区间 $[L, R]$ 与当前区间的 $mid$ 的大小，如果 $L \leq mid$，则递归查询左子区间 $[l, mid]$，如果 $R > mid$，则递归查询右子区间 $[mid + 1, R]$。

例如我们要查询 $[1, 7]$，先考察线段树结点 $1$，它的 $mid$ 为 $4$，于是左子区间和右子区间都要递归查询：

- 左子区间 $[0, 4]$ 的 $mid$ 为 $2$，继续递归查询左子区间和右子区间；
    - 区间 $[0,2]$ 还要继续往下查询，右子区间 $[3,4]$ 被待查询区间覆盖，直接返回；
- 右子区间 $[5, 9]$ 的 $mid$ 为 $7$，继续递归查询左子区间 $[5, 7]$，发现区间 $[5, 7]$ 被待查询区间 $[1, 7]$ 完全覆盖，于是直接返回；

最后返回的区间为 $[1,1], [2,2],[3,4],[5,7]$，和为 $35$。

代码实现：
```cpp
int Query (int idx, int l, int r, int L, int R) { // [L, R] 表示待查询区间
    if (L <= l && R >= r) { // 当前区间被待查询区间完全覆盖
        return seg[idx];
    }
    int sum = 0;
    if (L <= mid) {
        sum += Query(2 * idx, l, mid, L, R); // 递归查询左子区间，左子区间索引为 2 * idx
    }
    if (R > mid) {
        sum += Query(2 * idx, mid + 1, r, L, R); // 递归查询右子区间
    }
    return sum;
}
```

对线段树的单点修改，也是一层层遍历线段树，修改对应区间的和即可，如果只有单点修改而不存在区间修改，那么一般用树状数组就能解决，因此这里就不给出单点修改的实现了。

## 带 Lazy 标记的线段树

前面提到，常规的线段树，个人认为相比树状数组其实没什么优势，时间复杂度的常数还大，占用空间也大，假设待处理的数组 $nums$ 的 $size()$ 为 $n$，那么我们一般要开一个长度为 $4n$ 数组来存储线段树。

即 `int seg[4 * n] = {0};`。

那为什么说线段树支持 $O(\log n)$ 时间复杂度的区间修改呢，这就需要 Lazy 标记出马了。

`int todo[4 * n] = {0};`，这里的 $todo[idx]$ 就是所说的 Lazy 标记了。

Lazy 标记，简单来说，就是通过延迟对子节点信息的修改，从而减少可能的不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点 $idx$ 对应的区间在某一次操作中被更改，同时更新 $seg[idx]$，但是，我们选择**先不更新子节点的信息**，而是等到 $idx$ 的区间被“破坏”时，再更新子区间，这里说的区间被破坏，就是指我们要**更新**或者**查询** $idx$ 区间对应的子区间的情况。

例如，第一次更新，我们需要对区间 $[0, 4]$ 都 $+1$，经过遍历，我们知道区间 $[0, 4]$ 对应的 $idx$ 是 $1$，因此我们更新 `seg[1] += 5;`，同时将 `todo[1] += 1;`，这就是给 $idx = 1$ 打上了 Lazy 标记。

下一次更新或者查询，我们要对区间 $[3, 4]$ 都 $+2$，显然它是区间 $[0, 4]$ 的子区间，因此发生了对区间 $idx = 1$ 的“破坏”，于是我们需要把 Lazy 标记往区间 $[0, 4]$ 的左子区间和右子区间传递，因此我们更新 `seg[2] += 3, seg[3] += 2;`，同时将 `todo[2] += todo[1], todo[2] += todo[1], todo[1] = 0;`。

从递归的角度上来说，我们还是处于 $idx = 1$ 的这一层，然后继续递归右子结点，到了 $idx = 3$，更新 `seg[3] += 2 * 2;`，同时将 `todo[3] += 2;`。

带 Lazy 标记的更新操作具体实现如下：

```cpp
int seg[4 * n] = {0}, todo[4 * n] = {0};

void Update(int idx, int l, int r, int L, int R, int add) {
    if (L <= l && R >= r) {
        todo[idx] += add; // 更新 Lazy 标记
        seg[idx] += add * (r - l + 1); // 更新线段树
        return;
    }
    int mid = l + (r - l) / 2;
    if (todo[idx] != 0) { 
        // 说明当前区间存在 Lazy 标记。
        // 我们要查询的区间没有完全覆盖当前区间，必然还要往下递归
        // “破坏”了当前区间，因此将 Lazy 标记传递到左子区间和右子区间
        todo[2 * idx] += todo[idx];
        seg[2 * idx] += todo[idx] * (mid - l + 1);
        todo[2 * idx + 1] += todo[idx];
        seg[2 * idx + 1] += todo[idx] * (r - mid);
        todo[idx] = 0;
    }
    if (L <= mid) {
        Update(2 * idx, l, mid, L, R, add); // 递归更新左子树
    }
    if (R > mid) {
        Update(2 * idx + 1, mid + 1, r, L, R, add); // 递归更新右子树
    }
    seg[idx] = seg[2 * idx] + seg[2 * idx + 1]; // 更新“更新了左右子树”之后的当前区间和
}
```

带 Lazy 标记的查询其实与更新类似，当查询区间完全覆盖当前区间时，直接 `return seg[idx];` 即可，因为当前区间的值已经是最新的了，只是子区间并没有更新（我们这里也不需要子区间的值）；

没有完全覆盖时，就跟更新操作一样，出现了“破坏”当前区间的情况，因此更将 Lazy 标记传递到子区间，再继续递归；

```cpp
int Query(int idx, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
        return seg[idx]; // 配合上面的 Update 可知，打上 Lazy 标记时，当前区间的值已经更新，只是没有更新子区间
    }
    int mid = l + (r - l) / 2;
    if (todo[idx] != 0) {
        // 说明当前区间存在 Lazy 标记。
        // 我们要查询的区间没有完全覆盖当前区间，必然还要往下递归
        // “破坏”了当前区间，因此将 Lazy 标记传递到左子区间和右子区间
        todo[2 * idx] += todo[idx];
        seg[2 * idx] += todo[idx] * (mid - l + 1);
        todo[2 * idx + 1] += todo[idx];
        seg[2 * idx + 1] += todo[idx] * (r - mid);
        todo[idx] = 0;
    }
    int sum = 0;
    if (L <= mid) {
        sum += Query(2 * idx, l, mid, L, R);
    }
    if (R > mid) {
        sum += Query(2 * idx + 1, mid + 1, r, L, R);
    }
    return sum;
}
```

## 动态开点线段树

前面讲到堆式储存的情况下，需要给线段树开 $4n$ 大小的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子结点。这样我们不再使用 $2 * idx$ 和 $2 * idx + 1$ 代表 $idx$ 结点的儿子，而是用 $ls$ 和 $rs$ 记录儿子的编号。总之，动态开点线段树的核心思想就是：**结点只有在有需要的时候才被创建**。

单次操作的时间复杂度是不变的，为 $O(\log n)$ 。由于每次操作都有可能创建并访问全新的一系列结点，因此 $m$ 次单点操作后结点的数量规模是 $O(m\log n)$ 。最多也只需要 $2n-1$ 个结点，没有浪费。

具体的实现留待后面碰到需要动态开点的情况再写吧。

## 时间复杂度分析

对区间查询 $[L, R]$，考虑 $[L, L]$ 和区间 $[R, R]$ 的到他们最近公共祖先的路径，所有划分的区间必然是这个路径上的结点的直接子结点，树的深度为 $\log n$，因此经过的点最多为 $2 * 2 * \log n$ 个，所以时间复杂度为 $O(\log n)$。

单点修改显然是 $O(\log n)$，区间修改在有 Lazy 标记的情况下，类似于区间查询。