的原理和实现。

不需要读者有太多前置知识。

但熟知

BIT

由于没有查阅到相关资料，本文中的称呼全是作者瞎起的，还请勿要见怪。

时间内完成简单末尾追加的数据结构，与它的一点树上扩展。

注：本文中提及的“线段树”均指朴素递归线段树。

序列版本不管是码长还是常数都打不过高级线段树。

---

inline">\(2^i-1\)。

用斜二进制表示一个数时，需要满足至多一位为二且低于此位者均为零，其余位不超过一。

定义一个斜二进制数的最低有效位是它最低位值非零的位。

我们将使用一种归纳构造的方式来生成每个自然数的斜二进制分解。

0

inline">\(2\times(2^i-1)=2^{i+1}-2\)，再加上新多出来的一就是

inline">\(2^{i+1}-1\)。

于是我们清除这两位并向前一位进一即可。

不难验证以此法生成的斜二进制分解符合它应有的性质。

个元素构建的后树。

注意最后一个元素不属于任何一棵子树，它是特别的——也正因如此，我们可以将一棵后树的根编号为它最后一个元素的下标。

不难发现，如果假设整个序列从一开始编号并把后树的每个节点的斜二进制写出，那么根管辖的斜二进制区间将是

inline">\((0,100\cdots0]\)，左子树的管辖区间是

(0,10\cdots0]\)，右子树的管辖区间是

inline">\((10\cdots0,20\cdots0]\)。

我们不难证明，一个点

inline">\(j=i-\textit{skew\_lowbit}(i)\)，其中

inline">\(\textit{skew\_lowbit}(i)\)

进行斜二进制分解并用一系列后树来维护整个序列。

类似这样。

src="https://cdn.luogu.com.cn/upload/image_hosting/m5nrmb29.png"

loading="lazy">

inline">\(\textit{tr}_i\)：序列上

inline">\((i-\textit{skew\_lowbit}(i),i]\)

下标的元素合并后的结果（本质上是在后树上的子树“和”）。

inline">\(\textit{lb}_i\)：

class="math

inline">\(i-\textit{skew\_lowbit}(i)\)。

inline">\(\textit{tf}_i\)：点

（这几个东西在缩写之前分别是：array，tree，left_bound，tree_fa***r。

）

inline">\(\textit{tr}_i\)

inline">\(\textit{tr}_i\)，俗称

会有零个还是两个儿子，我们的手段相当暴力：遍历所有子树进行累和。

指出应该实现得更精细一点所以也写了一版没那么暴力的，效率差距不大：
可能需要变化，我们仿照斜二进制分解的归纳构造操作就行。
对于最低有效位为二的情况，我们可以简单地找到新加点的两个儿子；对于最低有效位不为二的情况，新加点没有儿子。
获取一个数
inline">\(i-\textit{lb}_i\)
是以它为根的后树的大小加一以二为底的对数。
不难发现每个点是不超过
的正整数。
特别地，我们定义零的高度是全局最高高度加一。
inline">\(h_{\textit{lb}_{\textit{lb}_i}}\ge
inline">\(h_r<x\)。
而根据上面的第一条，走第一个分支之后，至多再走一步第二个分支，一定会再回到第一个分支（否则连走两步之后
{cin.tie(nullptr)->sync_with_stdio(false);cin
>>
不难发现，该算法在简洁方面对比线段树有较大优势，功能强度方面介于树状数组与线段树之间。
常数应该不小。
它的作用？
总之大概能提供一个新的选择吧。
写起来比线段树快，比树状数组逻辑清晰（不需要前缀和差分的转）。
事实上这个东西还能上树。
不难发现每个点拖一个区间这个事情可以直接挂在每个点上往祖先去拖。
不难发现这样依然可以在
的时间内刻画出树上的一条路径。
另一方面，序列上需要倍增的场景其实并不多见，即使有也许多为双向，但树上倍增一般都是往祖先，这使得它可以更好地适应形如
n)\)，同时代码相当简短，在大部分情况下可以作为树上倍增的上位替代。
功能性除了支持动态加叶子是优势以外一般不如树剖，但时空常数和码量均更优（笔者个人实现的时间是树剖的三分之一），同时逻辑也更清晰。
严格劣
初始化非常简单：
同时可以看到其实逻辑和倍增是很类似的，易于配套理解。
城池攻占
inline">\(\textit{lb}\)，跳不了就跳爹：
{cin.tie(nullptr)->sync_with_stdio(false);n
rd();for
https://www.luogu.com.cn/problem/U421630。
同时这个东西还可以用来写全局平衡二叉树。
但这个时候我们会意识到一个很难受的事情：根的位置被固定了，无法再保证每个点子树大小和父亲的关系。
但是这个事情我们魔怔一下就能解决：把本来的左右儿子之间插一个中儿子就行，等于是一个点有仨儿子，其中中间那个的子树大小为一。
那么我们的性质就又没问题了。
写出来会比朴素
GBST
{cin.tie(nullptr)->sync_with_stdio(false);cin
>>
的指出，直接把中儿子塞到左儿子里复杂度也是对的，因为一个点的爷爷权和一定至少是自己的两倍所以树高依然是
{cin.tie(nullptr)->sync_with_stdio(false);cin
>>
具体有啥更多的应用可能还有待进一步发掘。
感觉是个非常适合引入
role="contentinfo">
本文来自博客园，作者：chu_yh，转载请注明原文链接：https://www.cnblogs.com/chu-yh/p/19181128