目录
树套树
树状数组套树状数组
简介
一般用与维护二维矩阵，码量以及常数小，通常涉及差分。
模板题
维护一个矩阵，支持以下操作：
- 将以 $(r_1,c_1),(r_2,c_2)$ 为顶点的矩阵内全部元素加上 $k$
- 输出 $(r_1,c_1),(r_2,c_2)$ 为顶点的矩阵内全部元素的和
考虑二维差分，设矩阵元素 $a_{x,y}=\sum_{i=1}^x\sum_{j=1}^y b_{i,j}$，则
\begin{equation}S_{i,j}=\sum_{x=1}^r\sum_{y=1}^c a_{x,y}=\sum_{x=1}^r\sum_{y=1}^c\sum_{i=1}^x\sum_{j=1}^y b_{i,j}=\sum_{i=1}^r\sum_{j=1}^c (r-i+1)(c-j+1)b_{i,j}\end{equation}
展开得
\begin{equation}S_{i,j}=(r+1)(c+1)\sum_{i=1}^r\sum_{j=1}^c b_{i,j}-(c+1)\sum_{i=1}^r\sum_{j=1}^c ib_{i,j}-(r+1)\sum_{i=1}^r\sum_{j=1}^c jb_{i,j}+\sum_{i=1}^r\sum_{j=1}^c ijb_{i,j}\end{equation}
考虑分别维护以下四项
\begin{equation}\sum_{i=1}^r\sum_{j=1}^c b_{i,j},\sum_{i=1}^r\sum_{j=1}^c ib_{i,j},\sum_{i=1}^r\sum_{j=1}^c jb_{i,j},\sum_{i=1}^r\sum_{j=1}^c ijb_{i,j}\end{equation}
修改操作变为 $b_{r_1,c_1}+=v,b_{r_2+1,c_1}-=v,b_{r_1,c_2+1}-=v,b_{r_2+1,c_2+1}+=v$。
查询操作变为 $S=S_{r_2,c_2}-S_{r_1-1,c_2}-S_{r_2,c_1-1}+S_{r_1-1,c_1-1}$。
空间复杂度 $O(n^2)$，时间复杂度 $O(q\log^2 n)$。
线段树套线段树
简介
一般用于解决树状数组套树状数组无法解决的二维偏序问题，通常涉及权值线段树、动态开点等。
模板题
维护 $n$ 个可重集，支持以下操作：
- 将 $c$ 加入编号为 $[l\sim r]$ 的集合
- 查询编号为 $[l\sim r]$ 的集合的并集中第 $c$ 大的元素
考虑权值线段树套线段树，第一维维护每个数值，第二维维护每个集合在某个数值区间拥有的元素个数。
为防止爆内存，第二维线段树需要动态开点，同时考虑线段树标记永久化优化常数。
时空间复杂度均为 $O(q\log v\log n)$。
线段树/树状数组套名次树
简介
用于实现区间范围的名次树操作，空间复杂度 $O(n\log n)$。
模板题
线段树套名次树版本
线段树套名次树 $\text{rank}$、$\text{update}$、$\text{pre}$、$\text{suf}$ 操作和普通线段树类似，$\text{kth}$ 操作需要二分 $+$ $\text{rank}$ 操作。
$\text{rank}$、$\text{update}$、$\text{pre}$、$\text{suf}$ 操作时间复杂度为 $O(\log^2 n)$，$\text{kth}$ 操作时间复杂度 $O(log^2 n\log v)$。
树状数组套名次树版本
树状数组套名次树 $\text{rank}$、$\text{update}$ 操作和普通树状数组类似，$\text{kth}$ 操作需要二分 $+$ $\text{rank}$ 操作， $\text{pre}$、$\text{suf}$ 操作需要 $\text{rank}+\text{kth}$。
$\text{rank}$、$\text{update}$ 操作时间复杂度为 $O(\log^2 n)$，$\text{pre}$、$\text{suf}$、$\text{kth}$ 操作时间复杂度 $O(log^2 n\log v)$。
权值线段树套名次树版本
转换一下思路，考虑外层维护权值，内层维护位置。那么 $\text{rank}$ 操作查询 $0\sim v-1$ 区间的满足条件的点的个数。
$\text{kth}$ 操作类似在线段树上跑类似名次树的操作，$\text{update}$ 操作先删除后插入，其他操作基于这两个基础操作即可得到。
空间复杂度 $O\left(n\log v\right)$，所有操作时间复杂度 $O\left(\log n\log v\right)$。
树状数组套权值线段树
简介
功能类似线段树/树状数组套名次树。
其实权值线段树和名次树在功能上有许多相同点，权值线段树码量相对较少，但空间复杂度多一个 $O(\log v)$。
模板题
该题等价于维护一个数组，支持一下操作：
- 修改某个点的点权
- 询问满足位置在 $[l_1,r_1]$ 且权值在 $[l_2,r_2]$ 范围内的点个数和点权和。
树状数组的每个节点的权值线段树维护区间 $[x-\text{lowbit}(x)+1,x]$ 的权值分布，每个权值记录点个数和点权和。
空间复杂度 $O(n\log n\log v)$，单次操作时间复杂度 $O(\log n\log v)$。
