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

线段树 の 实现

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

题目示例

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

  • 给定 l, r 和 x，让 a 中 [l, r] 区间内的每一个数加上 x（区间加）。
  • 给定 l, r，求 （区间求和）。

朴素实现 / Bruteforce

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

线段树 / Segment Tree

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

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

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

存储方式

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

对于区间 [l, r]​，可以将其均分为两段，设 ​，那么可以将 [l, mid]​ 和 [r, 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。

    则其长度最大的儿子的长度为 。

    那么设树高为 h，有 这个式子迭代 h 次之后等于 1。

    因为上式 ，那么有 那么容易解得 h = O(log n)，那么一般认为 h = ⌈log n⌉。

空间复杂度

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

1 + 2 + 4 + ⋯ + 2⌈log n⌉ ≤ 2⌈log n⌉ + 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); // 儿子都已经好了，将其信息合并至父结点
}

时间复杂度为 Θ(n)。

时间复杂度证明 1

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

时间复杂度证明 2

递归函数的时间函数为 ​。

那么在主定理中 a = b = 2，logba = log22 = 1，ϵ 可以取 (0, 1] 范围内的数字，满足主定理的第一条情况，所以 T(n) = Θ(n)。

区间修改

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

暴力修改 / Bruteforce

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

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

懒标记 / Lazy Tag

考虑引入懒标记（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] 对应的结点的 lzy ← 5，并且更新两个结点的区间和，同时向上回溯 pushup。

修改后的线段树：

区间查询

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

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

Trick 1：权值线段树

Trick 2：动态开点线段树

线段树 の 运用