0. 普适技巧
-
动态开点：节省空间。
-
标记永久化：分块的块标记本质就是这个。可以节省空间。
1. 区间最值 & 历史区间最值
2. 二维线段树
-
二维区间静态：二维 ST 表
-
二维前缀动态：二维树状数组
-
二维区间动态：二维线段树
3. 可持久化线段树
可持久化的本质是对每一次操作的前缀和数组。而主席树则是一个数列上的权值前缀和数组，可用于解决区间权值问题。
例题：
-
P2617 Dynamic Rankings：由于主席树的本质是前缀和，可以用树状数组实现动态修改。此时的代码已看不见可持久化的影子了。
-
Sequence II：巧妙，但先咕。
-
To the moon：使用标记永久化以节省空间。