【详细介绍】一种基于斜二进制的序列&树上数据结构

UnyieldingTrilobite · 2023-12-12 15:54:35 · 算法·理论

简版。这个文大概是详细地讲讲上面那篇东西里第二种 ds 的原理和实现。不需要读者有太多前置知识。但熟知 BIT 原理将对理解本文有较大帮助。

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

作者自己胡的×要是重复造轮子了就当搬运吧，感觉挺适合往 OI 里搬。

本文将介绍一种可以在 O(\log n) 的时间内支持单点修改区间查询，并能够在 O(1) 时间内完成简单末尾追加的数据结构，与它的一点树上扩展。

注：本文中提及的“线段树”均指朴素递归线段树。序列版本不管是码长还是常数都打不过高级线段树。

• 斜二进制

斜二进制是一种奇怪的进制。它从低到高第 i\ge1 位位权为 2^i-1。用斜二进制表示一个数时，需要满足至多一位为二且低于此位者均为零，其余位不超过一。定义一个斜二进制数的最低有效位是它最低位值非零的位。

我们将使用一种归纳构造的方式来生成每个自然数的斜二进制分解。0 的斜二进制是 0。我们假设已经对于 n 生成了它的斜二进制分解，那么 n+1 的斜二进制将在此基础上进行分类：

不妨这是第 i 位，那么乘上二的位值即为 2\times(2^i-1)=2^{i+1}-2，再加上新多出来的一就是 2^{i+1}-1。于是我们清除这两位并向前一位进一即可。

在第一位上加一即可。

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

这么讲可能比较抽象，我们来举点例子。

• 0 的斜二进制是 0。

• 1 的斜二进制是 1。因为 0 的最低有效位不为二。

• 2 的斜二进制是 2。因为 1 的最低有效位不为二。

• 3 的斜二进制是 10。因为 2 的最低有效位为二，向前进一。

• 4 的斜二进制是 11。因为 10 的最低有效位不为二。

• 5 的斜二进制是 12。因为 11 的最低有效位不为二。

• 6 的斜二进制是 20。因为 12 的最低有效位为二，向前进一。

• 7 的斜二进制是 100。因为 20 的最低有效位为二，向前进一。

• 8 的斜二进制是 101。因为 100 的最低有效位不为二。

• 9 的斜二进制是 102。因为 101 的最低有效位不为二。

• 10 的斜二进制是 110。因为 102 的最低有效位为二，向前进一。

• 11 的斜二进制是 111。因为 110 的最低有效位不为二。

• 12 的斜二进制是 112。因为 111 的最低有效位不为二。

• 13 的斜二进制是 120。因为 112 的最低有效位为二，向前进一。

总之大概就是这样。

• 后树

一棵后树维护一个长度为 2^n-1 的序列，其中 n\ge 1。

后树的根管辖整个区间，根的左子树是区间的前 2^{n-1}-1 个元素构建的后树，右子树是区间的接下来 2^{n-1}-1 个元素构建的后树。注意最后一个元素不属于任何一棵子树，它是特别的——也正因如此，我们可以将一棵后树的根编号为它最后一个元素的下标。

不难发现，如果假设整个序列从一开始编号并把后树的每个节点的斜二进制写出，那么根管辖的斜二进制区间将是 (0,100\cdots0]，左子树的管辖区间是 (0,10\cdots0]，右子树的管辖区间是 (10\cdots0,20\cdots0]。我们不难证明，一个点 i 为根的子树的管辖区间的左端点 j=i-\textit{skew\_lowbit}(i)，其中 \textit{skew\_lowbit}(i) 表示 i 在斜二进制下的最低有效位。

• 数据结构

我们考虑将 n 进行斜二进制分解并用一系列后树来维护整个序列。类似这样。

我们对于每个下标 i 维护四个东西：

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

我们以下将对几个常见操作分别说明。以和为例。

• 节点更新

在除了 \textit{tr}_i 未知以外所有必要信息均已知的情况下计算 \textit{tr}_i，俗称 pushup。由于并不知道 i 会有零个还是两个儿子，我们的手段相当暴力：遍历所有子树进行累和。

void pushup(int x) {
  tr[x] = a[x];
  for (int y = x - 1; tf[y] == x; y = lb[y]) tr[x] += tr[y];
}

有群 u 指出应该实现得更精细一点所以也写了一版没那么暴力的，效率差距不大：

void pushup(int x) {
  if (int p = x - 1; p == lb[x])
    tr[x] = a[x];
  else
    tr[x] = a[x] + tr[p] + tr[lb[p]];
}

• 末尾追加