浅谈线段树

文章同步发布于洛谷，建议前往洛谷查看。

前言

蒟蒻终于学会线段树（指【模板】线段树 $1$）啦！

线段树思想

我们先来考虑 P3372（基础线段树模板题）给的操作：

1. 区间修改（增加）
2. 区间查询（求和）

很重要的一点是，两者是交叉的，要不然可以使用好写时间复杂度又优秀又好吃的前缀和秒了。

$\mathcal{O}(1)$ 是困难的，所以我们思考可不可以 $\mathcal{O}(\log \mathbf{n})$ 实现。

分段

目标

我们可以把一个区间分割成 $\mathcal{O}(\log \mathbf{n})$ 个小区间（这一点非常重要），如果每个区间都可以 $\mathbf{\Theta }(1)$ 完成（当然也很重要，但是如果是均摊 $\Theta (1)$ 也行），则总时间复杂度为 $\mathcal{O}(\log n)$。

较为失败的分段

我们的第一反应是把整个序列分割成几块，但是这样显然是不行的，哪里没割我们就可以把区间的一个端点设置为那个点，然后就无法分割了。如果把整个区间分割成每一个长度都是 $1$，则和数组无异，分割成的块数是 $\mathcal{O}(\mathbf{n})$ 的。

看起来不太有希望，但是我们可以换种思路。

线段树思想

一个位置可以被多个区间包含，而分割的方法是类似二进制。

这样做的好处：一个数字 $\mathbf{k}$ 有 $\mathbf{\Theta }(\log \mathbf{k})$ 个二进制位，完美符合我们“一个序列被分割成 $\mathcal{O}(\log k)$ 个小序列”的要求。

这，就轮到线段树出场了。

这里插一句，为了发扬 STL 的传统美德，我们这里使用 $[a,b)$ 左闭右开区间，同时下标从 $0$ 开始。

我们假设序列长度是 $2^k$：

• 一个线段是 $[0,2^k)$
• 一个线段是 $[0,2^{k-1})$
• 一个线段是 $[2^{k-1},2\times 2^{k-1})$
• 一个线段是 $[0,2^{k-2})$
• 一个线段是 $[2^{k-2},2\times 2^{k-2})$
• 一个线段是 $[2^{k-1},3\times 2^{k-2})$
• 一个线段是 $[3\times 2^{k-2},4\times 2^{k-2})$
• …

我们把它以树的形式组织起来：

• $[0,2^k)$
  • $[0,2^{k-1})$
    • $[0,2^{k-2})$
      • …
      • …
    • $[2^{k-2},2\times 2^{k-2})$
      • …
      • …
  • $[2^{k-1},2\times 2^{k-1})$
    • $[2^{k-1},3\times 2^{k-2})$
      • …
      • …
    • $[3\times 2^{k-2},4\times 2^{k-2})$
      • …
      • …

或者，使用 Graph Editor？为了不让文字太长，这里令 $k=3$。

)

空间复杂度 $\Theta (k{2}^k)$，若 $n=2^k$ 则为 $\Theta (n\log n)$，可以完美承受。

这里，我们每一个节点不仅记录 $[l,r)$ 范围，还要记录一个东西：范围里所有数字的和，以下称作 $S$。

复杂度假了

假设整个区间为 $[0,8)$，我们要把 $[3,6)$ 这个区间的所有数字加一，我们可以：

• 把区间 $[0,8)$ 的 $S$ 加 $3$；
• 把区间 $[0,4)$ 的 $S$ 加 $1$；
• 把区间 $[2,4)$ 的 $S$ 加 $1$；
• 把区间 $[3,4)$ 的 $S$ 加 $1$；
• 把区间 $[4,8)$ 的 $S$ 加 $2$；
• 把区间 $[4,6)$ 的 $S$ 加 $2$；
• 把区间 $[4,5)$ 的 $S$ 加 $1$；
• 把区间 $[5,6)$ 的 $S$ 加 $1$。

看起来加了很多，复杂度真的是正确的吗？

很不幸，把区间内所有数字加上某个数字的时间复杂度为 $\mathbf{\Theta }(\mathbf{n}\log \mathbf{n})$，还不如直接在数组上操作呢。

那么，这个思路就不行了吗？当然不是，我们刚才已经看到过这个思路的一次绝处逢生，为什么这一次就不行？

我们注意到，把 $[4,6)$ 加 $2$ 可以不涉及到原来的区间就推出后面的把 $[4,5)$ 和 $[5,6)$ 加一这两件事。

小 trick？

所以，我们有一个优化的小 trick（至于为什么要加双引号，待会儿就知道了）：在每次区间加的时候，如果是把整个区间加某个值，则先记录下来要加，并不把下面的整个子树都加上某一个值。

事实上，专门用来记录这个值的变量叫做 $\text{lazytag}$，以下为了节省 $\text{KATEX}$ 的码量，则把它称作 $\text{tag}$（$\text{KATEX}$ 中 \text 内怎么加粗啊？/fn）

那么，加上这个 $\text{tag}$ 之后，变成了什么样呢？

• 把区间 $[0,8)$ 的 $S$ 加 $3$；
• 把区间 $[0,4)$ 的 $S$ 加 $1$；
• 把区间 $[2,4)$ 的 $S$ 加 $1$；
• 把区间 $[3,4)$ 的 $S$ 加 $1$；
• 把区间 $[4,8)$ 的 $S$ 加 $2$；
• 把区间 $[4,6)$ 的 $S$ 加 $2$；
• 把区间 $[4,6)$ 的 $\text{tag}$ 加 $1$。

看起来还是很多，但是我们惊喜的发现，如果在整个区间中都加上 $v$，我们只需要把 $[0,8)$ 的 $\text{tag}$ 加上 $v$ 即可。

接下来进入 hack 模式。

hack！

hack $1$：左边少一个元素

也就是 $[1,n)$。

分成两部分：$[1,\frac{n}{2})$ 和 $[\frac{n}{2},n)$，第二部分直接改一下 $\text{tag}$，$\Theta (1)$ 处理掉了。

第一部分分成两部分：$[1,\frac{n}{4})$ 和 $[\frac{n}{4},\frac{n}{2})$，第二部分直接改一下 $\text{tag}$，$\Theta (1)$ 处理掉了。

第一部分分成两部分：$[1,\frac{n}{8})$ 和 $[\frac{n}{8},\frac{n}{4})$，第二部分直接改一下 $\text{tag}$，$\Theta (1)$ 处理掉了。

第一部分分成两部分：$[1,\frac{n}{16})$ 和 $[\frac{n}{16},\frac{n}{8})$，第二部分直接改一下 $\text{tag}$，$\Theta (1)$ 处理掉了。

以此类推，时间复杂度：$T(n)=T(\frac{n}{2})+\Theta (1)$，显然 $T(n)=\Theta (\log n)$，也就是时间复杂度是 $\mathbf{\Theta }(\log \mathbf{n})$。

完美接招。

hack $2$：右边少一个元素

完美接招，把左边的稍微改改，变成每次第一部分直接 $\Theta (1)$ 处理掉了，时间复杂度 $\mathbf{\Theta }(\log \mathbf{n})$。

hack $3$：左右边都少一个元素

本来以为可以成功 hack 的，但是分成两半之后我们发现：

左边：相当于 hack $1$。

右边：相当于 hack $2$。

然后 $2\times \Theta (\log n)=\mathbf{\Theta }(\log \mathbf{n})$，又是一次完美地应对。

如何查询

显然，只能修改还不行，还得查询。

查询也就不难了，按照相似的方式，在树上递归求解，遇到和原本序列完全一样的直接加。

时间复杂度？我们不乱 hack 了，直接求时间复杂度吧。

时间复杂度

首先感性理解一下，层数是 $\Theta (\log n)$ 的，所以时间复杂度是 $\mathcal{O}(\log n)$ 的。下面是严谨的证明，不想看可以跳过。

有几种情况：

1. 序列和当前节点负责区间完全重合，直接返回，时间复杂度 $\Theta (1)$，不会继续递归。
2. 序列左端点就是目前节点负责的区间左端点，右端点不到区间中点。此时递归可能会变成情况 $1,2,3,4$。
3. 序列左端点就是目前节点负责的区间左端点，右端点恰好为区间中点。此时递归可能会变成情况 $1$，也就是时间复杂度还是 $\Theta (1)$。
4. 序列左端点就是目前节点负责的区间左端点，右端点超过区间中点。此时左边递归可能会变成情况 $1$，右边递归可能变成情况 $2,3,4$。
5. 序列右端点就是目前节点负责的区间右端点，左端点不到区间中点。此时递归可能会变成情况 $1,5,6,7$。
6. 序列右端点就是目前节点负责的区间右端点，左端点恰好为区间中点。此时递归可能会变成情况 $1$，也就是时间复杂度还是 $\Theta (1)$。
7. 序列右端点就是目前节点负责的区间右端点，左端点超过区间中点。此时右边递归可能会变成情况 $1$，左边递归可能变成情况 $5,6,7$。
8. 区间左端点和右端点都不是目前节点负责的左右端点，但是范围符合，左边可能递归成 $5,6,7$，右边可能是 $2,3,4$。
9. 区间左端点和右端点都在左半部分，可能递归为 $8,9,10$
10. 区间左端点和右端点都在右半部分，可能递归为 $8,9,10$

是不是看的有点晕？配合图片理解一下，黑色代表节点负责的区间，黑色中间的线代表中点，蓝色代表查询的点。

第一种：

第二种：

第三种：

第四种：

第五种：

第六种：

第七种：

第八种：

第九种：

第十种：

看个文章怎么跟个打音游一样

我们发现：只有第八种需要担心——有两个递归，可能导致时间复杂度变为 $\Theta (n)$。当然，第 $9$ 和第 $10$ 也需要担心，但是如果第 $8$ 种解决了，这两种也就迎刃而解了。

我们发现，一旦经过一次第 $8$ 中，就必然不会再经过第 $8,9$ 或 $10$ 种了。所以，如果我们把第 $1\sim 7$ 种和第 $9,10$ 中当做两个组的话，那么 $8$ 就是连接这两个组的桥梁。其中，第一个组花费的时间是 $\mathcal{O}(\log n)$ 的，第二个组也是，而“桥梁”最多被调用一次，所以最终时间复杂度是 $\mathcal{O}(\log n)+\mathcal{O}(\log n)+2\mathcal{O}(\log n)+\mathcal{O}(1)=\mathcal{O}(\log \mathbf{n})$。

查询时间复杂度也是 $\mathcal{O}(\log \mathbf{n})$ 的。

修改时间复杂度

我们发现和查询几乎没有区别，原本时间复杂度假掉的原因只是第一种情况会变成和第八种一样的 $T(n)=2T(\frac{n}{2})+\Theta (1)$，并且会变成两个第一种，时间复杂度直接废掉。加入 tag 之后就好啦！

时间复杂度证明和上述相同，是 $\mathcal{O}(\log n)$ 的。

这真的只是一个小 trick 吗？当然不是，这就是线段树的精髓，可以说，上面讲的思想就是线段树的灵魂，而这个 lazytag 就是线段树的骨架，缺一不可。

tag 的细节

在查询和修改时，如果一个标记已经有了 tag，那么这个 tag 可能会被使用，则需要把子树的标记加上本身的标记，然后修改 $S$，然后把标记清空，这一过程称作把标记下放（pushdown）。

代码

动态分配内存，然而静态开点。

// 需要 C++20 的 <bits> 头文件中的 bit_ceil 函数，作用是找到最小的 >= x 的 2 的幂，如果没有 C++20 也可以手写。// 线段/区间
template<typename T>
class segment
{
public:T l, r; // [l, r)size_t size() { return r - l; } // 长度bool fail() { return l >= r; } // 是否不合规template<typename Han_Si_Ying>friend bool operator==(const segment<Han_Si_Ying>& x, const segment<Han_Si_Ying>& y) { return x.l == y.l && x.r == y.r; } // Han_Si_Ying：？
};// 区间交
template<typename T>
segment<T> seg_and(segment<T> l1, segment<T> l2)
{return { max(l1.l, l2.l), min(l1.r, l2.r) };
}template<typename _Valt>
class segtree
{class segnode{public:segment<size_t> seg; // 负责区间_Valt s, tag; // S, lazytagsegnode* lp = nullptr, * rp = nullptr; // 左右子树void pushdown() // 下放标记{s += tag * seg.size();if (lp) lp->tag += tag;if (rp) rp->tag += tag;tag = 0;}};segnode* rt;void init(segnode* root, size_t l, size_t r) // 初始化{root->seg = { l,r };root->s = root->tag = _Valt();if (l + 1 == r) return;else{init(root->lp = new segnode, l, (l + r) >> 1);init(root->rp = new segnode, (l + r) >> 1, r);}}_Valt inn_query(segnode* root, segment<size_t> seg) // 区间查询{root->pushdown(); // 下放懒标记if (root->seg == seg) return root->s;segment<size_t> segl = seg_and(root->lp->seg, seg), segr = seg_and(root->rp->seg, seg); // 区间交_Valt sum = 0; // 和if (!segl.fail()) sum += inn_query(root->lp, segl);if (!segr.fail()) sum += inn_query(root->rp, segr);return sum;}void inn_add(segnode* root, segment<size_t> seg, _Valt val) // 区间修改{root->pushdown();if (root->seg == seg){root->tag += val;return;}root->s += val * seg.size();segment<size_t> segl = seg_and(root->lp->seg, seg),segr = seg_and(root->rp->seg, seg);if (!segr.fail()) inn_add(root->rp, segr, val);if (!segl.fail()) inn_add(root->lp, segl, val);}
public:segtree(size_t sz){sz = bit_ceil(sz); // 需要 2 的幂rt = new segnode{ 0, sz };init(rt, 0, sz);}_Valt query(size_t l, size_t r){return inn_query(rt, { l, r + 1 });}void add(size_t l, size_t r, _Valt x){inn_add(rt, { l, r + 1 }, x);}
};