浅谈如何用块状数组高效实现加强版普通平衡树

· · 算法·理论

前言

自古以来我们就有多种实现普通平衡树的方法,但大多要么实现复杂,要么效率堪忧。本文介绍了一种兼具高效性和实操性的树状数组 + 块状数组的解法。

一:整体思路

将元素按从小到大分成若干个块,块内初始有 B 个元素,最多有 2B 个元素,且块内元素也是有序的,同时开一个树状数组维护块的大小的前缀和。

二:核心变量

:::

四:复杂度分析

操作 时间复杂度 说明
预处理 O(n)/O(n\log n) 基数排序 / sort
find_block O(\log \frac{n}{B})
find_pos O(\log B)
split 单次 O(\frac{n}{B} + B),均摊 O(\frac{n}{B^2}) 单次建树状数组 O(\frac{n}{B}) + memcpy O(B),至少要 insert O(B) 次才会触发
remove 单次 O(\frac{n}{B}),均摊 O(\frac{n}{B^2})
build_fw O(\frac{n}{B})
add_fw / sum_fw O(\log \frac{n}{B})
insert / erase 均摊 O(B + \frac{n}{B^2}+\log \frac{n}{B}) memmove O(B) + split O(\frac{n}{B^2}) + 树状数组 O(\log \frac{n}{B})
get_rank / get_prev / get_next O(\log B+\log \frac{n}{B})
get_kth O(\log \frac{n}{B})
clear O(1)

当 B 取 n^{\frac{1}{3}} 时可以做到 O(n^{\frac{1}{3}}) 修改,O(\log n) 查询,实测当 B 取 200 到 500 时较优。
空间复杂度:pool 的空间约为 4n,a 的空间约为 n,其它数组可忽略不计,总复杂度 O(n)。

五:实测(用的是上面那一份代码)

洛谷上 P6136 跑了 2.29s,最优解第一页。
本机用 WorkBuddy 测的,n = 10^5,m = 10^6。 | 解法 | 随机 | 高重复 | 滑动窗口 | |---|---:|---:|---:| | 分块(本文) | 0.188s | 0.188s | 0.133s | | SBT | 0.418s | 0.201s | 0.281s | | AVL 树 | 0.418s | 0.191s | 0.254s | | 旋转 Treap | 0.634s | 0.203s | 0.216s | | WBLT | 0.640s | 0.548s | 0.442s | | FHQ Treap | 0.791s | 0.747s | 0.216s | | pbds 红黑树 | 0.793s | 0.573s | 0.331s | | Splay | 0.919s | 0.289s | 0.255s | | 权值线段树+离散 | 1.320s | 1.014s | 1.065s | | 替罪羊树 | ❌ 栈溢出 | ❌ 栈溢出 | 0.234s |

六:优劣分析

优点

  1. 常数小。
  2. 时空复杂度低(相较于普通块状链表)。

    缺点

  3. 码量相对于平衡树较大。
  4. 无法区间操作。

    七:为什么这么快

  5. 缓存局部性好,mx,fw 和当前操作的块常驻 L1,而平衡树节点散布主存。
  6. memmove 和 memcpy 批量搬运。
  7. 树状数组本身常数低。
  8. 全静态数组。

    八:如何继续优化

    将树状数组再分一次块,修改时只将树状数组后半更新,批量重建,SIMD 等,但以上操作均会增大码量,故在此略去不表。