浅谈线段树优化

发布于 2021-10-14  3.01k 次阅读


本文将讲解一些线段树优化方法.

讲解的先后顺序按照我认为的难度排序。
受篇幅约束,较难的例题将不会在本文中直接给出题解,只给出我写的题解的博文链接和优化部分的简单说明。

在数点问题中使用 CDQ 分治代替高维线段树

这一优化相对常见。

我们通常使用 $D-1$ 维线段树解决 $D$ 维数点问题,其时间复杂度为 $O((\log n)^{D-1})$,空间复杂度为 $O(n^{D-1})$。

考虑使用 CDQ 分治优化其空间复杂度。CDQ 分治的一个经典应用就是在 $O(\log n)$ 时间复杂度内将 $D$ 维数点问题降为 $D-1$ 维数点问题。我们可以考虑将其中 $k$ 层线段树替换为 $k$ 层 CDQ 分治,时间复杂度仍为 $O((\log n)^{D-1})$,空间复杂度降至 $O(n^{D-k-1})$。

例题:陌上花开

题意

给出 $n$ 个三元组 $a_i=(x_i,~y_i,~z_i)$,定义 $a_i$ 的价值为满足 $i \neq j$ 且 $x_j \le x_i,~y_j \le y_i,~z_j \le z_i$ 的 $j$ 的数量。请你求出价值为 $0 \sim n-1$ 的三元组的数量。

$n \le 10^5,~x_i,y_i,z_i \le 2 \times 10^5$

题解

三维偏序模板题。将所有三元组按照 $x_i$ 递增顺序排序,然后对这个序列进行 CDQ 分治。每次递归时计算左半区间内所有三元组对右半区间内的每个三元组产生的贡献,该问题为二维数点问题,直接用树状数组或是线段树解决即可。时间复杂度 $O(n (\log n)^2)$,空间复杂度 $O(n)$。

例题:[Ynoi2016] 镜中的昆虫

题意

维护一个长为 $n$ 的序列 $a_i$,有 $m$ 次操作:
1. 将区间 $[l,~r]$ 的值修改为 $x$。
2. 询问区间 $[l,~r]$ 出现了多少种不同的数。

$n,m \le 10^5,~1 \le a_i \le 10^9$

题解

我的题解

其中用到该优化的部分:

在经过一些操作后,我们需要维护二维单点修改和二维数点,空间复杂度不允许使用二维线段树。与上一题相同,在 CDQ 分治时使用左半区间的修改操作更新右半区间的查询操作即可,该问题为二维数点问题,可以使用树状数组或是线段树完成。

线段树底层分块

只有很少的题目强制要求使用该优化,但是该优化可以在任何情况下通过增加运行时长来减少线段树的空间占用。在空间限制紧张而时间限制宽松的题目中能够有一定的用处。

一般情况下线段树的叶子节点只维护原序列上的一个元素的信息,线段树结点数量为 $O(n)$,当线段树结点上维护的信息较多时容易占用过多内存。此时可以考虑让线段树叶子结点维护长度为 $B$ 的区间而非长度为一的区间。这一操作可以让线段树结点数量从 $O(n)$ 降至 $O(\frac n B)$。可以根据题目中具体的时间复杂度和空间复杂度,结合代码常数情况,手动调整 $B$ 使代码拥有较为均衡的运行时长和空间占用。

由于 $B$ 值与线段树结点数量相关,而时间复杂度同样与结点数量相关,在一些题目中也可以找到一个合适的 $B$ 值使得在时间复杂度不变的情况下减小空间复杂度。

所有线段树都可以使用该优化,这里只展示一个较难的例题。

例题:[Ynoi2007] rgxsxrs

题意

给定一个长为 $n$ 的序列 $a$,需要实现 $m$ 次操作:

  1. 1 l r x:表示将区间 $[l,~r]$ 中所有 $>x$ 的元素减去 $x$。
  2. 2 l r:表示询问区间 $[l,~r]$ 的和,最小值,最大值。

$n,m \le 5 \times 10^5,~1 \le a_i,x \le 10^9$

题解

我的题解

其中用到该优化的部分:

在进行一些操作后,我们有 $\log a_i$ 棵深度为 $\log n$ 的线段树,所有线段树上共有 $n$ 个叶子节点,每个节点上维护的信息的空间占用为 $O(1)$,每棵线段树上的查询数量为 $O(n)$。总时间复杂度 $O(n \log n \log a_i)$,空间复杂度 $O(n \log a_i)$。考虑将所有线段树底层按 $\log a_i$ 大小分块,空间复杂度 $O(\frac n {\log a_i} \log a_i)=O(n)$,时间复杂度 $O(n \log n \log a_i + \frac n {\log a_i} \log n (\log a_i)^2)=O(n \log n \log a_i)$。可以看到在时间复杂度没有变化的情况下有效减小了空间复杂度。


我缓慢吐出一串啊吧啊吧并不再想说话