从零开始的树套树浅谈

——by dsfz l1ll5
树套树 数据结构 OI

写在前面的话

有问题的话请留言 D 我...
树套树是一个很暴力的数据结构...

前置技能

1. 一颗有志于虐暴全世界数据结构傻逼题的心。
2. 一颗愿意听我这个菜逼口胡半天不睡觉的心。
3. 熟练掌握树状数组、线段树和平衡树等基础一维数据结构。

问题

T1：

对于一个一维序列 $A$ ， 记其中下标为 $i$ 的元素为 $a_i$ 。支持如下操作：

1. 给定 $i$ ，使 $a_i=a_i+k$
2. 给定 $l$ ， $r$ ，求 $\sum_{i=l}^{r} a_i$

$n\leq 10^5， q\leq 10^5$

sol：地球人都会做，可以用树状数组简单维护。

对于一个二维数组 $A$ ， 记其中下标为 $(i,j)$ 的元素为 $a_{i,j}$ 。支持如下操作：

1. 给定 $x$ ， $y$ ，使 $a_{x,y}=a_{x,y}+k$
2. 给定 $l$ ， $r$ ，$L$ ， $R$ 求 $\sum_{i=l}^{r} \sum_{j=L}^{R} a_{i,j}$

$n\leq 1000， q\leq 10^5$

sol：地球人不一定都会做了，不过智商在 1 以上的地球人还是都会做。
这是刚刚那个简单问题的二维情况，对于刚刚的问题我们用树状数组差分维护前缀和，所以类比的考虑，我们可以依旧用树状数组差分维护二维的前缀和，一个矩形拆成四个两条边在坐标轴上，一个顶点为源点的矩形，容斥即可。

具体怎么写呢？该怎么跳 $lowbit$ 还是怎么跳，看一眼代码就懂了。

这玩意局限性很大：首先支持的操作很少，其次空间是 $O(n^2)$ 的，基本上没啥用。

T2：

对于一个一维序列 $A$ ， 记其中下标为 $i$ 的元素为 $a_i$ 。支持如下操作：

1. 给定 $l$ ， $r$ ，使对于所有 $i \in [l,r]$，$a_i=k$
2. 给定 $l$ ， $r$ ，求 $\sum_{i=l}^{r} a_i$

$n\leq 10^5， q\leq 10^5$

sol：地球人都会做，可以用线段树简单维护。

对于一个二维数组 $A$ ， 记其中下标为 $(i,j)$ 的元素为 $a_{i,j}$ 。支持如下操作：

1. 给定 $l$ ， $r$ ，$L$ ， $R$ ，使得对于所有 $x \in [l,r] ， y \in [L,R]$ ， $a_{x,y}=k$
2. 给定 $l$ ， $r$ ，$L$ ， $R$ ，求对于所有 $x \in [l,r] ， y \in [L,R]$ ，最大的 $a_{x,y}$ 。
   强制在线
   $n\leq 100000， q\leq 10^5$

sol：地球人不一定都会做了，智商在 2 以上的地球人看完下面的字就会做了。

运用树套树的思想，故名思议，一棵树套一棵树，进一步的说，对于套在外面的树上代表 $[l,r]$ 的区间，维护这个矩阵的第 $l$ 到第 $r$ 行的信息。 具体怎么维护呢，再用一棵套在里面的线段树去维护，内层树上代表 $[L,R]$ 的区间维护了这个矩阵的第 $l$ 到第 $r$ 行，第 $L$ 列到第 $R$ 列的信息。
也就是说，对于外层线段树，每个节点上挂了一棵内层线段树维护行信息，内层线段树正常维护列信息。

（没图， YY 下就好了）

这样，每次矩形操作的时候先在外层找到行对应的区间，再在这些区间维护的线段树中找到对应的列就可以确定这个区间了。
显然单次操作的复杂度是 $O(log_n^2)$ 的，因为外层找到了 $log_n$ 个区间，每个区间在内层确定列区间的复杂度是 $O(log_n)$的。
直接修改即可。

好，现在大家会二维线段树了。

好像有哪里不对。

啊，的确不对。我们考虑信息的合并，内层线段树是正常的，直接 $pushdown$ 和 $pushup$ 即可。
但是考虑外层线段树，树上的一个节点维护了一棵线段树...

没法高效的合并两颗线段树的信息做到 $pushup$ ，更没办法快速下传一个 $pushdown$ 的标记。

那怎么办呢？

标记永久化

一个不太常见的可以用于实现线段树的方法：
考虑每次操作，我们需要 $pushdown$ 推下去这个区间的信息 ， $pushup$ 将儿子们的信息合并。
其中每个节点的标记如果 $pushdown$ 后就简单的清空它。

任性一点，不想这么写。

存在这样一个事实：一个区间 $[l,r]$ 打上某个需要下传的标记后，这个区间是一定要受到这个区间的影响的。

所以为什么一定要下传标记呢？在递归的同时更新答案，查询的时候通过了一个有标记的区间，就带上这个标记，用它更新答案好了。

存在这样一个事实：一个区间 $[l,r]$ 进行某个修改后，需要上传修改的影响，这个区间的父亲一定要受到这个区间的影响的。

所以为什么一定要上传信息呢？在找到修改区间的过程中，在路径上打一个上传信息的标记，查询的时候用这个标记更新好了。

这么说起来有点晕。

标记永久化即在修改时路径更新上传标记，找到区间后更新下传标记。
查询时路径上带上下传标记查询，找到区间后用上传标记更新即可。

仔细想想应该能懂了。

这样不需要子树信息合并和下传信息，就可以用来维护外层线段树了。

回到刚刚的问题，矩形赋值和矩形最值查询。
由于数据范围较大，需要动态开点。在此给出一个外层线段树的代码实现，内层线段树即普通的线段树，有些题解也用了标记永久化，没有必要，常数上也不是很优。

max[x]用于维护上传标记，tag[x]用于维护下传标记。
r_tag[x] r_max[x]用于维护内层线段的根节点，因为动态开点了。
其实外层树一般不用动态开点，这题我乱写的。

这样这个问题就解决了，显然时空复杂度都是 $O(nlog_n^2)$的。
BZOJ 1513 [POI2006]Tet-Tetris 3D

二维线段树换一种说法就是线段树套线段树，其他是树套树也是类似的。
我们来换一道题。

T3

有 $N$ 个位置，$M$ 个操作。操作有两种：

每次操作如果是 $1$ $a$ $b$ $c$ 的形式表示在第 $a$ 个位置到第 $b$ 个位置，每个位置加入一个数 $c$
如果是 $2$ $a$ $b$ $c$ 形式，表示询问从第 $a$ 个位置到第 $b$ 个位置，第 $c$ 大的数是多少。

$n,m \leq 50000$
这是个经典题，可以整体二分做，我们现在强制在线它。

直接维护每个下标都有什么数是困难的，那怎么办呢。

询问第 $k$ 大是多少这种东西是树套树常见套路之一，外层维护一棵权值线段树即可，这是一个类似二分答案的过程。
对于外层权值线段树中权值为 $[l,r]$ 的区间，维护一棵普通的线段树，这颗线段树只维护权值在 $[l,r]$ 的数。
即对于题目中的区间加一个数 $c$ ，若 $c \in [l,r]$ 则区间加一，否则不变。
这样每次在外层类似平衡树的二分，内层查询区间和即可。

这样就能嘴巴 AC 了，实际上此题有坑，爆 int ， 需要用 unsigned int ，而且读入数据有负数需要转化一下... 还是有点麻烦的。

时空复杂度均为 $O(nlog_n^2)$
BZOJ 3110 [Zjoi2013]K 大数查询

T4

单点赋值，询问区间第 k 大。
$n,m \leq 10^5$

啊，如果没有修改操作就是主席树裸题了。
然而有修改。

一个朴素的想法是暴力修改所有影响到的版本的信息，不过一个点修改影响了它的所有前缀，即 $O(n)$ 颗树，那么暴力的复杂度是 $O(nlog_n)$ 的，不能接受。

对于前缀信息的维护，可以想到利用树状数组高效维护。
于是我们用一个树状数组将所有版本的根串起来，每次修改跳一下 $lowbit$，修改经过的那些树即可。
这一步是 $O(log_n^2)$ 的。
询问操作如何处理呢？同步的在那 $log_n$ 棵树上爬即可，每次合并这些线段树对应节点的信息，复杂度也是 $O(log_n^2)$ 的。
空间复杂度为 $O(nlog_n^2)$。
由于使用了树状数组，常数不大。
BZOJ 1901 Zju2112 Dynamic Rankings

T5

给一个序列，支持如下操作：

1. 查询 $k$ ，在区间 $[l,r]$ 内的排名。
2. 查询区间 $[l,r]$ 内排名为 $k$ 的值。
3. 修改下标为 $i$ 的数的数值。
4. 查询 $k$ 在区间 $[l,r]$ 内的前驱。
5. 查询 $k$ 在区间 $[l,r]$ 内的后继。

其中，前驱定义为小于 $x$ ，且最大的数。后继定义为大于 $x$，且最小的数。

$n,m \leq 50000$

如果查询操作没有在区间 $[l,r]$ 内的限制，地球人都会做。

有一个朴素的想法：
外层开一棵区间线段树，其中每个维护 $[l,r]$ 的区间均维护一棵平衡树，这颗平衡树维护这个区间内的信息。

嗯，很好做了...?
发现操作 2 不太好搞，由于区间被分解成了线段树上的多个子区间，平衡树上没法查询了。
所以可以考虑二分答案，转化为判定性问题即可。
但是时间复杂度是 $O(log_n^3)$ 的了，太不优雅。

所以考虑好搞一点的做法：
发现修改操作不改变序列形态，其中查询区间第 $k$ 大和单点赋值操作就是我们刚刚提到的带修改主席树。
那是不是就可以做了啊？
发现前驱后继求出排名后 +1 查询数值即可，也就是说实现操作 2 就好了。（此处注意后继需排除相等情况）
关于操作 2 ，与上个做法内层维护的平衡树不同，我们现在内层维护的是主席树，它们的形态都是一样的，所以可以方便的合并信息以像平衡树的那么查询。
所以就可以做了，时间复杂度 $O(nlog_n^2)$，空间复杂度 $O(nlog_n^2)$。
常数还是不大，优化下输入输出轻松卡到 BZ 第一页，貌似 RK1 也是这么做的。

还有一个貌似可行的做法是外层权值线段树内层套区间线段树维护，我没写，不过想一下就知道时空常数都很大...
据说需要套内存回收才可过。

由于是浅谈，就到此为止了...
下面口胡一点奇奇怪怪的东西。

树套树套树

会了树套树就会写这个了，但是几乎没人写。
代码复杂度太高了...同时空间开销也很大。

树套树套树套树

会了树套树套树就会写这个了，但是真没人写了。
代码复杂度 $\rightarrow inf$ ，时空复杂度、常数 $\rightarrow inf$ 。

怎么优雅的解决上面两个问题呢？
K-Dtree 就好啦，空间复杂度是 $O(n)$ 的，时间复杂度虽然较劣但是常数小...
在这里可以学到。

树套树套树套树套树套树...套树

$n^2$暴力即可...

刚刚那几个题的代码基本在我博客都有...嗯