省流：本文将介绍用指针实现线段树，并介绍如何在题目中运用线段树解决问题。

线段树 の 实现

线段树一般用于维护区间信息。

题目示例

要求维护一个序列 $\{a_n\}$，实现两种操作：

• 给定 $l,r$ 和 $x$，让 $a$ 中 $[l,r]$ 区间内的每一个数加上 $x$（区间加）。
• 给定 $l,r$，求 $\sum_{i=l}^{r}a_i$（区间求和）。

朴素实现 / $\textbf{Bruteforce}$

• 前缀和：发现有区间求和，容易想到用前缀和 $O(1)$ 维护。但是对于区间加，最坏情况下要修改整个前缀和序列，时间复杂度为 $O(n)$。
• 差分：发现有区间加，容易想到用差分 $O(1)$ 维护。但是对于区间求和，每次需要计算一次差分序列的前缀和，时间复杂度为 $O(n)$。

线段树 / $\textbf{Segment Tree}$

有没有一种可以均衡两个操作复杂度，每次操作是 $O(\log n)$ 的数据结构呢？

线段树是将序列分治的过程，并且将分治的过程记录下来。

线段树维护的信息需要满足可合并性，即可以从儿子的信息得到父亲的信息。

存储方式

线段树将序列中若干个区间在树上用结点来表示，其中 $[1,n]$（在下文的讨论中 $n$ 均表示序列长度）为树的根。

对于区间 $[l,r]$​，可以将其均分为两段，设 $\text{mid}=\left\lfloor\dfrac{l+r}{2}\right\rfloor$​，那么可以将 $[l,\text{mid}]$​ 和 $[r,\text{mid}]$​​​ 分别作为当前结点的左右儿子。

对于上面的题目，可以这样设计结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct TreeNode {
  long long w; // 区间之和
  size_t l, r; // 当前区间的左右端点
  TreeNode *lson, *rson; // 左儿子与右儿子的指针
  
  TreeNode() {
    w = 0;
    l = r = -1;
    lson = rson = nullptr; // 空指针
  }
  
  TreeNode(size_t _l, size_t _r) {
    w = 0;
    l = _l, r = _r;
    lson = rson = nullptr;
  }
};

下面是一颗维护 $[1,7]$ 的线段树形态：

性质

1. 对于线段树上的任一结点，儿子数量为 $0$ 或 $1$​，不存在只有一个儿子的情况。

   证明

   非常显然。

2. 一个长度为 $n$ 的序列建立的线段树只有 $(2n-1)$ 个结点。

   证明

   首先线段树上必然有 $n$ 个叶子结点。

   每两个叶子结点会合并，添加一个结点，此时没有父结点的点数减一。

   最后没有父结点的点数为 $1$，即根节点，所以添加了 $(n-1)$ 个结点。

   故总共有 $(2n-1)$ 个结点。

3. 一个长度为 $n$ 的序列建立的线段树的高度为 $O(\log n)$（$O(f(n))$ 的意思是与 $f(n)$ 同阶）。

   证明

   首先对于一个结点 $[l,r]$，设其长度 $t=r-l+1$。

   则其长度最大的儿子的长度为 $\left\lfloor\dfrac{t+1}{2}\right\rfloor$。

   那么设树高为 $h$，有
   $$ \dfrac{\dfrac{\dfrac{n+1}{2}+1}{2}+1}{2}\dots $$
   这个式子迭代 $h$ 次之后等于 $1$。

   因为上式 $\le \dfrac{n+h}{2^h}$，那么有
   $$ \dfrac{n+h}{2^h}=O(1) $$
   那么容易解得 $h=O(\log n)$，那么一般认为 $h=\left\lceil\log n\right\rceil$。

空间复杂度

线段树是一个类似完全二叉树的结构，考虑从上至下的每层结点数量之和，得到

$$ 1+2+4+\cdots+2^{\lceil\log n\rceil}\le2^{\lceil\log n\rceil+1} $$

一般结点数量接近 $4n$。

建线段树

树是递归定义的，所以也可以递归建树。

线段树需要从儿子的信息合并得到父亲的信息，考虑设计一个辅助函数：

1
2
3

void pushup(TreeNode *u) {
  u->w = u->lson->w + u->rson->w;
}

这样就可以从儿子的区间和得到父亲的区间和了。

每次修改操作结束后都需要一次 pushup！

建树只需要将当前区间分为两部分，然后分别递归下去即可，详见代码。

1
2
3
4
5
6
7
8
9
10
11

// 假设根节点的 l,r 都已经设置好
void build(TreeNode *u) {
  if (u->l == u->r) { // 到达叶子节点
    u->w = a[u->l]; // 赋为 a 数组中对应的值
    return ;
  }
  auto mid = u->l + u->r >> 1; // 将区间分割为两半
  build(u->lson = new TreeNode(l, mid)); // 递归左儿子
  build(u->rson = new TreeNode(mid + 1, r)); // 递归右儿子
  pushup(u); // 儿子都已经好了，将其信息合并至父结点
}

时间复杂度为 $\Theta(n)$。

时间复杂度证明 1

容易发现每次调用 build 就新建了一个线段树结点，而结点数量为 $\Theta(n)$，那么时间复杂度也就是 $\Theta(n)$ 了。

时间复杂度证明 2

递归函数的时间函数为 $T(n)=2\times T\left(\dfrac n2\right)$​。

那么在主定理中 $a=b=2$，$\log_ba=\log_22=1$，$\epsilon$ 可以取 $(0,1]$ 范围内的数字，满足主定理的第一条情况，所以 $T(n)=\Theta(n)$。

区间修改

由于单点修改相当于修改一个区间 $[p,p]$​，所以仅讨论区间修改。

暴力修改 / $\textbf{Bruteforce}$

遍历区间内的每一个位置，然后在线段树上定位修改。

这样做的时间复杂度是 $O(n\log n)$ 的，甚至不如用数组维护。

懒标记 / $\textbf{Lazy Tag}$

考虑引入懒标记（$\textbf{Lazy Tag}$​），在结点处记录修改信息。

设当前递归到的区间为 $[l,r]$，需要修改的区间为 $[L,R]$，需要区间加上 $x$。

如果 $[l,r]$ 被 $[L,R]$ 完全包含，那么可以在 $[l,r]$ 所对应的结点上标记这颗子树需要 $+x$，并且更新当前结点的 w，然后直接返回。

每次访问到一个结点时，需要先将懒标记下放到子结点上，然后递归。

正确性比较显然。

举个例子

假设初始序列为 $\{1,5,4,2,3\}$，要对 $[1,4]$ 的每一个数加上 $5$​​。

---

线段树初始形态：

---

区间 $[1,4]$ 在线段树上一路递归下去发现可以划分为 $[1,3]$ 和 $[4,4]$ 两个序列。

此时将 $[1,3]$ 和 $[4,4]$ 对应的结点的 $\text{lzy}\gets5$，并且更新两个结点的区间和，同时向上回溯 pushup。

修改后的线段树：

区间查询

由于单点查询相当于查询一个区间 $[p,p]$​，所以仅讨论区间查询。

这里采用懒标记的实现方法。

$\textbf{Trick 1}$：权值线段树

$\textbf{Trick 2}$：动态开点线段树

线段树 の 运用