跳转至

线段树简介

线段树

  • 线段树的每个节点都代表一个 区间。
  • 线段树具有唯一的根结点，代表的区间是整个统计范围，如 \([1,N]\)。
  • 线段树的每个叶结点都代表一个长度为 \(1\) 的元区间 \([x,x]\)。
  • 对于每个内部结点 \([l,r]\)，他的左子结点是 \([l,mid]\)，右子结点是 \([mid+1,r]\)，其中\(mid=⌊\frac{l + r}{2}⌋\)。

线段树Tip

  1. 线段树是一棵非常漂亮二叉树，（除了最后一层外，是一棵满二叉树），因此我们采用堆的思想来存整棵树
    • 编号 x 的父节点：\(⌊\frac{x}{2}⌋\) ，常书写的代码：x >> 1
    • 编号 x 的左儿子：\(2x\) ，常书写的代码：x << 1
    • 编号 x 的右儿子：\(2x+1\) ，常书写的代码：x << 1 | 1

  2. 线段树的下一层都是把当前层进行平分 \(mid=⌊\frac{l + r}{2}⌋\)

    • 左区间为 \([l,mid]\)
    • 右区间为 \([mid+1,r]\)

    注意，线段树的两个子区间是不允许相交的

    这也决定了许多题的分块要进行额外的操作，使之区间不能相交

  3. 线段树一般开长度为 \(4N\) 的空间

    • 一个长度为 \(N\) 的区间，最终的叶结点，为 \(N\) 个
    • 先考虑理想状态下（包含最后一层，整个二叉树都是满二叉树），\(N\) 个叶结点的满二叉树有 \(N+\frac{N}{2}+\frac{N}4+⋅⋅⋅+2+1=2N−1\) 个结点。
    • 但是线段树的存储方式下，最后一层还会有盈余，最坏情况下，最后一层是倒数第二层（也就是满二叉树的倒数第一层）两倍的点，所以所以保存线段树的数组长度要不小于 \(4N\) 才能保证不会越界

线段树的区间修改与懒惰标记

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么。

如果要求修改区间 \([l,r]\)，把所有包含在区间 \([l,r]\) 中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。

懒惰标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。

仍然以最开始的图为例，我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个 \(t_i\)，表示该节点带的标记值。

最开始时的情况是这样的（为了节省空间，这里不再展示每个节点管辖的区间）：

现在我们准备给 \([3,5]\) 上的每个数都加上 \(5\)。根据前面区间查询的经验，我们很快找到了两个极大区间 \([3,3]\) 和 \([4,5]\)（分别对应线段树上的 \(3\) 号点和 \(5\) 号点）。

我们直接在这两个节点上进行修改，并给它们打上标记：

我们发现，\(3\) 号节点的信息虽然被修改了（因为该区间管辖两个数，所以 \(d_3\) 加上的数是 \(5 \times 2=10\)），但它的两个子节点却还没更新，仍然保留着修改之前的信息。不过不用担心，虽然修改目前还没进行，但当我们要查询这两个子节点的信息时，我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确。

接下来我们查询一下 \([4,4]\) 区间上各数字的和。

我们通过递归找到 \([4,5]\) 区间，发现该区间并非我们的目标区间，且该区间上还存在标记。这时候就到标记下放的时间了。我们将该区间的两个子区间的信息更新，并清除该区间上的标记。

现在 \(6\)、\(7\) 两个节点的值变成了最新的值，查询的结果也是准确的。

接下来给出在存在标记的情况下，区间修改和查询操作的参考实现。

区间修改（区间加上某个值）： 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void update(int l, int r, int c, int s, int t, int p) {
    // [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p
    // 为当前节点的编号
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c, b[p] += c;
        return;
    }  // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
    int m = s + ((t - s) >> 1);
    if (b[p] && s != t) {
        // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
        b[p] = 0;                                // 清空当前节点的标记
    }
    if (l <= m) update(l, r, c, s, m, p * 2);
    if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}

区间查询（区间求和）： 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int getsum(int l, int r, int s, int t, int p) {
    // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if (l <= s && t <= r) return d[p];
    // 当前区间为询问区间的子集时直接返回当前区间的和
    int m = s + ((t - s) >> 1);
    if (b[p]) {
        // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),
            b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
        b[p] = 0;                                    // 清空当前节点的标记
    }
    int sum = 0;
    if (l <= m) sum = getsum(l, r, s, m, p * 2);
    if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
    return sum;
}

如果你是要实现区间修改为某一个值而不是加上某一个值的话，代码如下： 

 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
void update(int l, int r, int c, int s, int t, int p) {
    if (l <= s && t <= r) {
        d[p] = (t - s + 1) * c, b[p] = c;
        return;
    }
    int m = s + ((t - s) >> 1);
    if (b[p]) {
        d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
            b[p * 2] = b[p * 2 + 1] = b[p];
        b[p] = 0;
    }
    if (l <= m) update(l, r, c, s, m, p * 2);
    if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}

int getsum(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return d[p];
    int m = s + ((t - s) >> 1);
    if (b[p]) {
        d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
            b[p * 2] = b[p * 2 + 1] = b[p];
        b[p] = 0;
    }
    int sum = 0;
    if (l <= m) sum = getsum(l, r, s, m, p * 2);
    if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
    return sum;
}

线段树的模版

pushup()：由子结点的信息来计算父结点的信息

build()：将一段区间初始化为线段树

modify()：修改

  • 单点修改（easy）

  • 区间修改（hard）：用到pushdown操作，懒标记思想

query()：区间询问（例如：查询 \([a,b]\) 区间）\(O(log⁡n)\) 最多是 \(4log⁡n\) 的时间，因为最坏有两条链

  1. \([l,r]⊃[T_l,T_r]\)，直接返回

  2. \([l,r]∩[T_l,T_r]≠∅\)，递归下去

    • \(l≤T_l≤r≤T_r\)：

      1. \(r≤T_{mid}\)：只递归左半边

      2. \(T_{mid}<r\)：递归左半边 + 递归右半边（但右子树完全包含，只递归一层就返回了）

    • \(T_l≤l≤T_r≤r\)：

      1. \(l≥T_{mid}\)：只递归右半边

      2. \(T_{mid}>l\)：递归右半边 + 递归左半边（但左子树完全包含，只递归一层就返回了）

    • \(T_l≤l≤r≤T_r\)：

      1. \(r≤T_{mid}\)：只递归左半边

      2. \(T_{mid}<l\)：只递归右半边

      3. \(l≤T_{mid}<r\)：递归左半边 + 递归右半边

  3. \([l,r]∩[T_l,T_r]=∅\)，不存在这种可能，因为初始区间包含了合法的所有范围。

回到页面顶部