线段树 (Segment Tree)

时间：2024-03-01 21:10:08

预备知识：树状数组 。

与树状数组 (Binary Index Tree, BIT, aka "二叉索引树") 类似，线段树适用于以下场景：

给定数组 a[n]， 并且要求 w 次修改数组，现有 q 次区间查询，每次区间查询包括 [l, r] 2 个参数，要求返回 sum(a[l, r]) 的值。

如果没有「修改元素」的要求，显然用前缀和是最好的。既然树状数组能解决上述场景，那么线段树比树状数组好在哪里呢？

  • 线段树可以在 \(O(\log{n})\) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
  • 树状数组适用于单点修改和区间查询。

显然，线段树比树状数组能力更强，树状数组能做到的，线段树同样能做到。

结构

线段树的本质是一棵基于数组表示的二叉树。

假设有一个大小为 5 的数组 \(a[5] = \{10, 11, 12, 13, 14\}\) ，记线段树为 \(d[n]\) ，下标均从 1 开始计数。那么该线段树的形态如下：

                  [1, 5]
               /          \
          [1,3]             [4,5]
         /     \           /     \
      [1,2]    [3,3]   [4,4]     [5,5]
     /     \
[1,1]       [2,2]
// 线段树的性质：叶子节点是数组元素

每个节点表示一个区间（亦即所谓的「线段」），线段树 \(d_i\) 记录的是这一区间的和：

d[1] = sum([1, 5]) = 60
d[2] = sum([1, 3]) = 33
d[3] = sum([4, 5]) = 27
d[4] = sum([1, 2]) = 21
d[5] = sum([3, 3]) = 12
d[6] = sum([4, 4]) = 13
d[7] = sum([5, 5]) = 14
d[8] = sum([1, 1]) = 10
d[9] = sum([2, 2]) = 11

前面提到，线段树的本质是基于数组表示的二叉树，那么节点 \(d_i\) 的左右孩子节点分别为 \(d_{2i}, d_{2i+1}\), 且根据线段树的形态，那么我们有：

\[d_i = d_{2i} + d_{2i+1} \]

根据这一递推公式，显然可以得知，线段树建立和修改是「自底向上」的。

建树

建立线段树的第一个问题：给定数组 \(a[n]\) ，那么线段树需要多大的空间？

分析

  • 线段树是一棵完全二叉树，其高度为 \(h = \lceil \log{n} \rceil\)，高度从 0 开始计数，这意味着该二叉树有 \(h+1\) 层。
  • 考虑最坏情况，线段树是一棵满二叉树，那么有 \(2^{h+1} - 1\) 个节点。

\[2^{h+1} - 1 \le 2^{h+1} \le 2^{\log{n} + 2} \le 2^{\log{4n}} = 4n \]

  • 因此，线段树的空间一般开 \(4n\) 大小。当然，调数学库精确算一下也是可以的 (if you want) 。

假设我们当前节点 \(d_i\) 表示的是区间 \([s, t]\) 之和，那么其左节点 \(d_{2i}\) 表示的是区间 \([s,\frac{s+t}{2}]\) ，其右节点 \(d_{2i+1}\) 表示的是区间 \([\frac{s+t}{2}+1, t]\) .

建树操作如下：

const int n = 5;
int nums[n + 1] = {0, 10, 11, 12, 13, 14};
vector<int> d;
void build(int s, int t, int idx)
{
    if (s == t)
    {
        d[idx] = nums[s];
        return;
    }
    int m = s + (t - s) / 2, l = 2 * idx, r = 2 * idx + 1;
    build(s, m, l), build(m + 1, t, r);
    d[idx] = d[l] + d[r];
}
int main()
{
    d.resize(4 * n, 0);
    build(1, n, 1);
}

区间查询

区间查询，即求出区间 \([l,r]\) 之和，或者求出区间的最大值、最小值等操作。

依旧以这个树为例子：

                  [1, 5]
               /          \
          [1,3]             [4,5]
         /     \           /     \
      [1,2]    [3,3]   [4,4]     [5,5]
     /     \
[1,1]       [2,2]

如果区间 \([l, r]\) 是线段树上的一个节点，那么这种查询是简单的，直接获取 \(d_1 = 60\) 即可。那如果要查询的区间不是对应于某个节点（即横跨若干节点），查询是怎么做到的呢？以查询区间 \([3, 5]\) 为例，可以拆分为 \([3,3]\) 和 \([4, 5]\) 这 2 个节点。

一般地，查询区间为 \([l, r]\) ，根据线段树的性质，最多可拆分为 \(\log{n}\) 个子区间（这些子区间要求是一个极大的子区间，即 \([4,5]\) 不用再进一步拆分为 \([4,4]\) 和 \([5,5]\) ）。

// [l, r] 为查询区间, [s, t] 为当前节点包含的区间
// idx 代表线段树的节点
int getsum(int l, int r, int s, int t, int idx)
{
    if (l <= s && t <= r)
        return d[idx];
    int sum = 0;
    int m = s + (t - s) / 2;
    if (l <= m) // 如果 [s, m] 与目标区间 [l, r] 有交集
        sum += getsum(l, r, s, m, 2 * idx);
    if (m < r)  // 如果 [m+1, t] 与目标区间 [l, r] 有交集
        sum += getsum(l, r, m + 1, t, 2 * idx + 1);
    return sum;
}

区间修改

如果要对 nums[i] 的值修改，那么线段树需要做出调整，任何包含 nums[i] 的区间都需要修改，复杂度是 \(O(\log{n})\) .

如果要对区间 \([a, b]\) 内数组元素做修改，显然，在线段树中，任何包括了 nums[a ... b] 中某一元素的区间都要修改一次，这时候复杂度为 \(O((b-a+1) \cdot \log{n})\) ，这个复杂度属实有点蚌埠住

相关文章