三月七树

主要是一个有点乐子的数据结构，并不是最优解法。

更新：三月七树也可以维护序列（可以替代线段树，单次 $\log n$，还可以支持序列插入删除等，加上这个的复杂度为 $\sqrt m$）。

省流：一种基于暴力重构的平衡树。

优点：常数小，好写好调好理解。

缺点：在特定数据下复杂度差。

约定 $n$ 为总元素个数，$m$ 为总操作次数，$B$ 为块长。

平衡树的一般操作可见这里。

我们注意到普通的二叉搜索树各操作的复杂度为 $O(h)$，$h$ 为树高，各种平衡树只是通过很多操作保证了 $h≈\log_2 n$，但这些操作大多很复杂。在这里，引入一种基于分块的方便的处理方式。我将其称为“三月七树”。

我们记录当前树高 $h$。在执行操作 $1$ 时，$h$ 有概率变大。当 $h\ge B$ 时， 我们将整棵树进行一次 DFS 。由于二叉排序树的性质，进行中序遍历的结果一定是排好序（从小到大）的，我们按照这个顺序将其记录下来。随后，对这个序列进行建树。考虑到（可能是我不知道）二叉排序树并没有什么快速建树的方法，我们对这个序列（依照有点类似树状数组的方式）建树，具体如下：

对于第 $i$ 个元素，令其位于从下往上第 $k$ 层（钦定叶子节点为 $0$），$k$ 为满足 $2^x|i$ 的最大整数。然后，若 $k\le \log_2 n$，向第 $k+1$ 层没有同时拥有左右子结点的节点连边。若该节点不存在，分两种情况：若下一个 $k+1$ 层的节点理应小于 $n$，向这个节点连边。否则，向第 $k+2$ 层节点连，若仍不存在，再次重复上述判断。

下面是 $n=17$ 时建出来的树。编号为这个元素的排名。

（9 和 11 号节点画反了，但是不太影响总体）

通过这种方式重构三月七树的复杂度为 $O(n)$ 的。以下为证明：

显然，对于某个确定的 $i$，$k$ 是可以 $O(1)$ 求出的。向 $k+1$ 层连边的复杂度为 $O(1)$。在我们首次向 $k+2$ 层连边后，不可能再次向 $k+1$ 层连边，因为在这种情况下，$k+2$ 层的节点排名一定在 $k+1$ 层之前，那么向上的过程是单调的。复杂度为 $n+\log_2 n=O(n)$。

重构后 $h=\log_2 n$。

其他操作与普通二叉树极度相似，不再赘述，同时因此三月七树的期望单次操作复杂度为 $O(\log n)$。

以下为最坏复杂度分析。

最坏情况下，输入单调。因此会出现最左（右）链特别长的情况。这种情况下单次操作最坏为 $O(h)=O(B)$，如果一直这么做，每 $B-\log_2 n$ 次会进行一次重构。复杂度为 $O(\dfrac{nm}{B-\log_2 n} +mB)$，前一项为重构复杂度。取 $B=\dfrac{n}{\sqrt m}+\log_2 n$（或还可以取 $\sqrt m$ 等），带入进去得到最坏复杂度 $\dfrac{nm}{B-\log_2 n} +mB=m\sqrt m+m\sqrt m+m\log_2 n=O(m(\sqrt m+\log n))$。够不到普通平衡树的水平，但是也达到分块了（还能简单的实现插入删除）。有点鸡肋，但是似乎有点用。大概可以稳定通过 $n,m\leq 2\times 10^5$ 的构造数据。

或许子树内重构可能比整棵树重构更优达到更好的复杂度？有兴趣的朋友可以研究研究。