数据结构：萌芽中的单调树
ltz761222
·
·
算法·理论
背景
我一直在想，我们有栈，便有了单调栈；我们有了队列，就有了单调队列，我们有了树……等等，好像还没有单调树！
于是我研究了三分钟，发现这玩意好像还叫做堆。于是我更新了一下思路，但一直没有结果。直到一天，我无意之间分析了一下最长上升子序列这个题，突然就想到了一种单调树，正文是我研究拓展之后的结果。
用途
单调树有很多用，支持动态的加入，删除，区间修改和区间查询。特别的，若没有删除操作支持求区间最值。
单调树的单次复杂度比较玄学，操作均基于为 \log {n}，但因为一些不好的原因，真实复杂度还需要各位去计算蒟蒻就不在这里班门弄斧了。
定义
我们想象中的单调树应该是什么样的？他一定如单调栈和单调队列一样，在某一角度来看能够一直单调。最简单的想法就是从根节点出发向下单调或者从叶子结点出发向上单调，但不难发现这两种是一样的。
若单调树是从叶子节点出发向上递增，那么他等同于从根节点出发向下递减。反之，如果单调树是从根节点出发向上递减，那么他等同于根节点向下递增。
为了方便，我们便规定单调树的单调顺序是由根节点出发，向下搜索。
于是定义如下：若有一颗有根树，他的每个节点都小于异或大于他的父亲节点，则这棵树是一颗单调树，他的起点是根节点，终点是所有叶子结点。
正如单调栈一般，我们需要在单调树内进行分类。
若一颗单调树的每个节点都大于他的父亲节点，则这棵单调树是单调加树。特别的，若这棵单调树的每个节点都严格大于他的父亲节点，则成这棵树是严格单调加树。
若一颗单调树的每个节点都小于他的父亲节点，则这棵单调树是单调减树。特别的，若这棵单调树的每个节点都严格小于他的父亲节点，则成这棵树是严格单调减树。
加入操作
我们任意选取单调树中的两条从根节点到叶子结点的路径（如图一的 0->3 和 0->4）
我们可以发现，这两条路径的上半部分重合，下半部分不一样（~~这不废话吗~~）。如果我们结合单调栈来看呢？会不会有不一样的发现呢？
我们先让 0->3 全部进入单调栈，因为单调树的定义，所以一定没有一个节点会出栈。此时的单调栈怎么变成 0->4 的形式呢？明显是让 3 号节点出栈，之后 4 号节点入栈即可。
先让原来的节点出栈，再让新的节点入栈，我们是不是见过这种操作？在单调栈中，若新加入的节点破坏了单调性，则我们就要执行和上面一样的操作。
于是，我们完全可以发挥人的本能，直接拿过来使用。加入一个节点之后，将栈的第二个节点作为新加入节点的父亲即可（若栈中只有一个节点则作为 0 号节点的儿子）。
下图图二、三是不出栈的情况，该操作加入了 1 号节点。
$\tiny{图二}$
$\tiny{图三}$
下图图四、五是出栈的情况，该操作中， 3 号节点破坏了单调性，使其出栈，之后 4 号节点入栈。
$\tiny{图四}$
$\tiny{图五}$
## 性质
经过加入操作之后，我们稍稍微整理一下单调树的性质，附带推理过程。
首先，对于每一个节点，我们模拟其在单调栈中的位置时不难发现这个节点很有可能多次处于倒数第二的位置，他便有多个儿子。
浓缩出第一条性质，叉性质：单调树是一颗多叉树。
其次，对于一个加入操作，若一个节点的儿子增多了，则加入操作之后该节点仍在栈内。因此，若一个节点所在子树的节点增多了，则说明这个子树有节点还在栈中。反之，若我们在加入操作时一个子树没有变化，则这个子树的节点全部出栈了，若不考虑其他操作，这个子树永远不会变化。
浓缩出第二条性质，止性质：若只考虑加入操作，则对于一个子树的操作只会是连续的一段。
最后，观察单调栈，一个节点加入后，栈的最后两个元素只会有两种情况：一是两个节点下标连续，二是两个节点下标不连续。但要注意的是，无论是哪一种情况，倒数二个节点的下标一定小于最后一个。
若我们将每一条连续的链单独分为一块，那么我们便可以得到一个神奇的性质（如图六）
$\tiny{图六}$
我们发现，每条链的终点都是叶子节点，这是巧合吗？
结合止性质，若最近加入的节点在下一次加入操作没有被更新儿子，则他不会再有儿子。又因为他是刚刚加入单调树的节点，所以他本来也没有儿子。综上，若只考虑加入操作，这个节点会一直是叶子节点。
浓缩出第三条性质，链性质：整颗单调树一定存在一种方案，使得整棵树被分为多条链，且链的下标连续，链的终点是叶子结点。
## 删除操作
第三条性质一看就很重要，但他的适用范围太小，只能考虑加入操作，属于半废品。但如果我们能让其他操作进行之后都能一直满足链性质呢？
我们可以先假设，之后再去验证可行性。
我们在别的数据结构中好像很少见到删除操作，这是为什么呢？我举个例子：单调树都会吧？不会的会树状数组也行。如果我们想要在这两个数据结构中删除节点，如果他们要求求和，把节点更改为 0 就可以了。还有一部分是求 max 的操作，这些操作基本没有删除的身影了，追根溯源还是因为太麻烦。
既然我们想要发明单调树，那么他一定要有特点才行。删除可以算特点吗？或许只是一个小凸起罢了，后面会有更加显著的特点。
进入正题。若我们删除了一个叶子节点，对整棵树没有任何影响，所以我们只需要考虑删除非叶子节点即可。同时，因为根节点是虚构的 0 号节点，也不需要考虑。
我们能不能将这个节点变成叶子节点呢？一个节点是否是叶子结点的依据便是有没有儿子，如果我们把他的儿子挪走，是不是就可以直接删除了呢？理论上是可行的。
我们把儿子挪到哪里呢？别忘了单调树的定义，易得若一个节点的父亲变成了他父亲的祖先，则这棵树仍是单调树。所以，只需要将该节点的儿子作为他父亲的父亲的儿子即可（如图七，我们删除了 2 号节点并将他的儿子的父亲更改成他父亲的父亲）
$\tiny{图七}$
为什么将儿子节点的父亲不更改成该节点的父亲呢？大家可以自己想一下，理由是破坏了链性质，这里不展开了。
## 更改操作
当我们修改一个节点时，因为节点的值大小与这棵树息息相关，所以我们要根据正负分类讨论。
举个例子你就明白了：假设在单调加树中，有一个节点 x ，我们令该节点的值加 3 ，那么对于他的儿子来说，他的父亲有可能会大于他，所以要换一个父亲。当我们将不合法的儿子移走之后，该节点已经不再与儿子矛盾了，所以并不需要操作。（下图图七进行了一次更改操作，使 2 号节点增大，导致儿子 3,4 号节点不合法，于是断开 2 号节点与儿子的边，并找到 0 号节点作为 3,4 的新父亲）
$\tiny{图七}$
反之，如果我们在单调加树中，令一个节点的值减小，那么他就有可能比父亲小，但对于他的儿子来说，这没有任何问题。因此，我们只需要让该节点另外再找一个父亲即可。（下图图九减小了 4 号节点的值，所以我们令 4 号的父亲是 4 号父亲 2 号的父亲即可）
$\tiny{图九}$
## 查询操作
查询操作主要是懒标记，这一块放在存储来讲，稍微过一下就好了。
查询前预处理原数组前缀和，这样答案=原区间和+区间内懒标记。
## 存储
当我们想要写代码的时候，会发现第一步的存储都写不出来。
这是正常的，因为本人也卡了好几天，最后才想出来。
纵观整个文案，可以发现全篇出现最多的就是一个字：链。
都知道单调树有链性质，每一条链的节点都是连续的。所以对于每一条链，不难想到只要知道了起点和长度就可以知道这条链上除去起点之外所有节点的父亲了。那么起点怎么办呢？多开一个超级祖先，表示起点的父亲。这样再加上链的和，正好凑成四元素。
加入时，判断最后两个节点是否连续。若连续，令新加入节点加入上一个节点的链，并修改这条链的链和以及长度。否则，我们需要多开一条链来存储不连续的新点。（可以看图六理解一下）
$\tiny{图六}$
接下来先说修改。修改需要我们预处理原数组的前缀和以及懒标记。因为一般情况下数组大小不会超过 $1e6$，所以可以直接开桶存储。懒标记分两类，第一类表示节点 a 增加 x ，第二类表示从 a 开始到这条链的结束全部增加 x ，这样可以完美处理单体和区间修改。
之后是删除。删除时只需要修改他的儿子的父亲。特殊的，对于与该节点处于同一条链的儿子，他需要新增一条链并修改原来这条链的长度和区间和。
查询都会了，直接原区间和+懒标记。
## 优化
懒标记是按照桶来存储的，那么如果我们想要求一个区间的懒标记会爆时间，因此如果各位有条件就可以用树状数组维护一下。
删除和其余一些地方出现了“选择一个合适的节点”这种字眼。我们没有必要一个一个去找，只需要找每一条链的起点就一定可以找到。
最后这种树很容易被单调上升异或单调下降卡成线性（即每个点自己就是一条链），所以发明一种类似平衡树的做法。
在我们的算法中，需要遍历每一条链，所以链越少，越算越快。所以在加入的时候搞一些幺蛾子，若本来就可以延续之前的链，就不管他。否则，更改该节点直至可以延续当前的链，并将更改值的相反数作为一个新点，即令 $new_{x}+new_{x+n}=a_{x}$ ，这样链的多少会大幅下降。下标大于 n 的 new 数组根本无需使用，用前缀和处理之后直接加上就可以了。
如果我们的 new 数组相差为 1 ，这时候每一次删除、修改都一定会增加一条链。数差越大，增加链的可能就越小。这样很容易联想到找一个较好的值。建议数差大于加入时的最大值，这样至少可以减去一般的叉，复杂度大大降低。
## 总结
这种树形结构目前仍在研究之中，我们希望经过高超的平衡算法，可以使得该树拥有 $\log{n}$ 个叶子节点。
若如此，区间操作的复杂度是 $\log {n}$，单点操作的复杂度是 $\log log {n}$ 的大常数，可以处理1e6以上的数据。