数据结构 - 再探线段树

基本操作

由于题目是从报名的课程中选取的，出于版权原因，只是记录一下思路，如确实需要可以与我邮件联系。

首先分析线段树中常见的函数。

• build(u, L, R): 递归对线段树进行初始化。
• pushup(u, L, R): 通过左右两个子节点的信息维护当前节点的信息。
• spread(u, data, L, R): 将修改应用到给定节点，并且处理懒标记。
• pushdown(u, L, R): 将懒标记通过 spread 下放。
• modify(u, data, l, r, L, R): 区间修改 / 单点修改(函数签名不太一样)。
• query(u, l, r, L, R): 区间查询 / 单点查询(函数签名不太一样)。注意操作子树前一定要进行 pushdown。

下面以一个稍复杂的题目为例。

普通线段树

例1

给定数列 $a_1, a_2, \dots, a_n$，进行 $m$ 次下列操作：

• 1 l r v 区间 $a_l\sim a_r$ 全部加 $v$；

• 2 l r v 区间 $a_l\sim a_r$ 全部乘 $v$；

• 3 l r 区间 $a_l\sim a_r$ 两两乘积之和。

经典的乘加操作，对于这种可以认为每一个操作都是 $a \gets xa+y$，这样我们就可以对两个不同的操作进行合并了。

然后考虑两两乘积之和应该如何形式化地表示，显然对于 $a,b,c$ 结果是 $ab+ac+bc$，所以 $a_l\sim a_r$ 应当是 $\sum_{l<i<j<r}a_ia_j$。

但是这样写并不好定量分析，所以进一步转化为 $\sum_{i=l}^r \sum_{j=i+1}^r a_ia_j$，对于节点 $u$，设 $c_u=\sum\sum a_ia_j$，$s_u=\sum a_i$。

Pushup

首先我们考虑如何通过子节点 $ls,rs$ 推父节点 $u$ 的值，显然的有：

$$\begin{aligned} s_u&\gets s_{ls}+s_{rs}\\ c_u&\gets c_{ls}+c_{rs}+\text{something} \end{aligned}$$

那么我们接下来看 $\text{something}$ 应该是什么。假设左边的所有元素是 $a_1,a_2,\dots,a_p$，右边是 $b_1,b_2,\dots,b_q$，那么交叉乘积应当是：

$$a_1b_1+a_1b_2+\cdots+a_1b_q+a_2b_1+a_2b_2+\cdots+a_2b_q+\cdots$$

不难看出它其实就是 $s_{ls}\times s_{rs}$，所以：

$$\begin{aligned} s_u&\gets s_{ls}+s_{rs}\\ c_u&\gets c_{ls}+c_{rs}+s_{ls}s_{rs} \end{aligned}$$

Spread & Pushdown

下面我们看如果每一个 $a_i\gets xa_i+y$ 这个式子会变成什么，其中令 $m=r-l+1$：

$$\begin{aligned} \sum_{i=l}^r \sum_{j=i+1}^r (xa_i+y)(xa_j+y)&= x^2\sum_{i=l}^r \sum_{j=i+1}^r a_ia_j+ \sum_{i=l}^r \sum_{j=i+1}^r xya_i+ \sum_{i=l}^r \sum_{j=i+1}^r xya_j+ \sum_{i=l}^r \sum_{j=i+1}^ry^2\\ &= x^2\sum_{i=l}^r \sum_{j=i+1}^r a_ia_j+ xy\sum_{i=l}^r a_i(r-i)+ xy\sum_{j=l}^r \sum_{i=l}^{j-1} a_j+ y^2\frac{m(m-1)}{2}\\ &= x^2\sum_{i=l}^r \sum_{j=i+1}^r a_ia_j+ xy\sum_{i=l}^r a_i(r-i)+ xy\sum_{j=l}^r a_j(j-l)+ y^2\frac{m(m-1)}{2}\\ &= x^2\sum_{i=l}^r \sum_{j=i+1}^r a_ia_j+ xy(m-1)\sum_{i=l}^r a_i+ y^2\frac{m(m-1)}{2}\\ \end{aligned}$$

注意，在交换求和顺序时，需要保证最终遍历到的 $(i,j)$ 是相同的，这里只需要保证 $i<j$ 就可以。

所以我们维护 $\sum a_i$ 与 $\sum\sum a_ia_j$ 就可以在常数的时间求出更新后的 $\sum\sum a_ia_j$ 了。

例2

维护一个数列 $a_i$，支持两种操作：

• 1 l r k d：区间加等差数列，即令 $a_l\gets a_l+k,a_{l+1}\gets a_{l+1}+k+d,\dots$
• 2 p：查询序列第 $p$ 个数 $a_p$。

这一类区间加数列的题目，可以考虑通过每个元素的位置来处理每一个位置需要的操作不一样这个问题。

具体地说，对于 $a_l\sim a_r$ 中的 $a_i$，它需要的操作是 $a_i\gets a_i+k+(i-l)d$，我们把加的部分抽出来：

$$\Delta =di+k-dl$$

不难发现，一项与位置 $i$ 有关，另一项是常数。所以我们维护两个标记 $t_1,t_2$ 表示 $i$ 的系数和常数项。

在更新区间和 $S_u$ 的时候，设它维护的区间是 $l\sim r$，显然有：

$$S_u\gets S_u+t_1\sum_{i=l}^r i+t_2(r-l+1)$$

这是可以在常数时间完成的更新。

例3

维护一个数列 $a_i$，支持两种操作：

• 1 l r：区间加数列 $1^2,2^2,\dots,(r-l+1)^2$；
• 2 l r：查询 $a_l\sim a_r$ 的和。

同样的思路，我们发现对于 $a_i$ 需要的操作是 $a_i\gets a_i+[i-(l-1)]^2$，我们把加的部分抽出来：

$$\Delta = i^2-2(l-1)i+(l-1)^2$$

可以看出，分别与 $i^2,i^1,i^0$ 有关。所以维护三个标记 $t_1,t_2,t_3$，在更新区间和 $S_u$ 时就可以：

$$S_u\gets S_u+t_1\sum_{i=l}^r i^2+t_2\sum_{i=l}^r i+t_3(r-l+1)$$

这里用一下 $\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$ 就可以了。

线段树二分

仓鼠的鸡蛋

有 $n$ 堆鸡蛋，每堆个数 $a_i$。

有 $n$ 个篮子编号 $1\sim n$，每个篮子最多放 $m$ 个鸡蛋，且最多放 $k$ 堆鸡蛋。

如果从 $a_1\sim a_n$ 每次都将该堆鸡蛋放到编号最小的，求每次放入的篮子编号。

这里有两个约束条件，其一是 $\sum a_i \le m$，其二是 $a_i$ 本身的个数 $\le k$。

我们可以这样思考，当某个篮子放的个数 $\ge k$ 时，直接把它装满，这样新来的鸡蛋就不会往里面放了，所以现在约束条件只有一个。

这里要求我们尽可能编号小，所以在查询可行位置时，如果能去左儿子就去，否则就去右儿子。

在叶子节点判断是否可行然后返回编号即可。

Little w and Discretization

给定一个长度为 $n$ 的数组 $1\le a_i\le 10^9$。

有 $m$ 次询问将 $a_l\sim a_r$ 离散化处理后，多少个元素和原来不同。

这里离散化后的值从 $1$ 开始取。

显然地，如果元素 $x$ 和原来相同，那么 $1\sim x$ 都应该在 $a_l\sim a_r$ 中出现。

也就是说我们要找到从 $1$ 开始最小的没有出现的那个元素 $k$。

这是一个类似 mex 的问题，使用值域线段树。

具体地做法是，将询问离线下来，保证每个询问的 $r$ 非严格递增，查询 $l$ 时就我们需要找到最小的 $k$ 使得它最后一次出现的位置 $<l$。

现在知道了 $k$，那么需要统计区间 $(l,r)$ 内 $\ge k$ 的值的数量。

对于数量，我们不难想到前缀和的思想，可以离线下 $l-1,r$ 统计前缀中 $\ge k$ 的元素的数量，也可以主席树。

势能线段树

势能分析

势能分析是一种均摊复杂度的分析方法，更详细的说明可自行搜索 OI-WIKI，这里简要说明一下。

假设一个数据结构的势能是 $\Phi\ge 0$ 且 $\Phi_0=0$，第 $i$ 次操作的实际代价为 $a_i$，那么均摊代价 $b_i$ 为：

$$b_i=a_i+\Phi_{i}-\Phi_{i-1}$$

我们将 $n$ 次操作求和，可以得到：

$$\sum_{i=1}^n b_i=\sum_{i=1}^n a_i+\Phi_n-\Phi_0\ge \sum_{i=1}^n a_i$$

因此最终的复杂度是比均摊复杂度的和 $\sum b_i$ 要小的。

我们需要找到合适的势能函数，将昂贵操作的代价与势能的减少量抵消掉，就可以算出一个正确的复杂度。

The Child and Sequence

给定长度为 $n$ 的数列 $a_i$，有三种操作：

1. 区间 $a_l\sim a_r$ 求和；
2. 区间 $a_l\sim a_r$ 对 $p$ 取模；
3. 单点修改。

需要用到取模的性质：$x\bmod p\le \frac{x}{2}(x\ge p)$，$x\bmod p=x(x<p)$。

证明第一条：由于 $x\bmod p<p$，那么 $x\bmod p<\lfloor x/p\rfloor p$，那么 $2(x\bmod p)<\lfloor x/p\rfloor p+(x\bmod p)=x$。

第二条显然，那于是我们可以记录一下区间 $u$ 的最大值 $m_u$，当最大值 $<p$ 时，区间 $u$ 无需操作。

现在我们考虑如何定义势能函数。由于每一次真正的取模操作都会至少减少一半，这个性质使得我们可以考虑以对数。

定义 $\Phi=\sum_{u} \log_2 m_u$，设暴力操作的节点的集合是 $A$，$m_u$ 为操作前区间 $u$ 的最大值，那么一次取模操作均摊复杂度为：

$$\begin{aligned} b_i&=O(\log n)+|A|+\Phi_i-\Phi_{i-1}\\ &\le O(\log n)+|A|+\sum_{u\in A} \log_2\frac{m_u}{2}-\sum_{u\in A}\log_2 m_u\\ &=O(\log n) \end{aligned}$$

然后求单点修改的均摊复杂度，设被修改的节点集合为 $A$，修改的值最大为 $V$：

$$\begin{aligned} b_i&=O(\log n)+\Phi_i-\Phi_{i-1}\\ &\le O(\log n)+\sum_{u\in A} \log_2V\\ &=O(\log n\log V) \end{aligned}$$

因此最终的复杂度是 $O(n\log n\log V)$。注意暴力操作的时候不要漏掉 pushup。

And RMQ

给定长度为 $n$ 的数列 $a_i$，有三种操作：

1. 区间 $a_l\sim a_r$ 按位与 $v$；
2. 单点修改；
3. 查询 $a_l\sim a_r$ 的最大值。

注意到与运算的性质，$a\operatorname{and}v$ 相当于把 $a$ 的某些位置设置为 $0$，这个“某些位置”就是 $v$ 中为 $0$ 的位置。

因此，如果整个区间 $v$ 为 $0$ 的位置都是 $0$，那么这个区间就不用操作。

所以我们维护一个区间的按位或，区间 $u$ 的按位或记作 $r_u$。

如果需要进行暴力操作，一定会把所有操作节点的 $r_u$ 删掉至少一个 $1$，因此势能定义为 $\sum_u \operatorname{popcount}(r_u)$。

与上一题相同，最终的复杂度同样是 $O(n\log n\log V)$，其中 $V$ 指 $a_i$ 的最大值。

区间开根号

给定长度为 $n$ 的数列 $a_i$，有两种操作：

1. 区间 $a_l\sim a_r$ 开根号下取整；
2. 区间求和。

我们记录区间 $u$ 的最大值 $m_u$，需要暴力操作的时候，我们希望势能的减少量与暴力的节点数量抵消掉。又因为 $\log_2\log_2\sqrt{m_u}=\log_2\log_2 m_u-1$，因此取 $\sum_u \log\log m_u$ 为势能函数。

那么，进行一次开根的均摊复杂度就是 $O(\log n)$。那最终的复杂度是 $O(n\log n)$ 吗？

这里有一个问题，就是我们建树之后的初始势能 $\sum_{u}\log \log m_u$ 并不为 $0$，而是 $O(n\log n\log \log V)$。

因此复杂度应当是 $O(\sum b_i+\Phi_0)=O(n\log n\log \log V)$。

上面两个题没有说这个的原因是，我们可以把建树操作当作进行了 $n$ 次单点修改，而这个题是没有单点修改的。