寻求支持对数时间定位与区间移至首尾的数据结构

存在这样的数据结构，核心是支持分裂（Split）和合并（Merge）操作的平衡二叉树，这类结构同时满足对数时间的元素定位和区间移动需求，完美平衡了vector和链表的优缺点。

核心原理 #

每个节点除了存储元素值，还记录其左右子树的总节点数（子树大小）。基于这个信息：

• 定位第k个元素：从根节点出发，通过比较左子树大小与k的关系，快速导航到目标节点，时间复杂度O(log n)。
• 区间移动操作：以将[i,j]移到头部为例，通过三步完成：
  1. 分裂：将整个树拆分为三部分：A（前i-1个元素）、B（第i到j个元素）、C（第j+1到末尾的元素）。
  2. 合并：按B → A → C的顺序合并这三部分，得到目标结构。
     整个过程的分裂、合并操作均为O(log n)时间，总复杂度O(log n)。

具体实现结构 #

1. Treap（树堆） #

• 结合二叉搜索树的有序性和堆的优先级特性，保证树的平衡。
• 分裂和合并操作基于优先级维护平衡，均为O(log n)最坏时间复杂度。
• 实现逻辑简单，适合快速开发。

2. Splay Tree（伸展树） #

• 通过伸展操作将访问/操作的节点移至根节点，具备局部性优化（频繁访问的元素会更快被访问）。
• 分裂、合并操作的均摊时间复杂度为O(log n)，实际性能在多数场景下表现优异。

3. 扩展AVL树 #

• 在标准AVL树的基础上维护子树大小信息，严格保证树的高度平衡。
• 分裂、合并操作的最坏时间复杂度为O(log n)，适合对稳定性要求高的场景。

示例操作（匹配你的需求） #

原数组：[1,4,34,67,2,3,15,78]（1索引），需将i=3到j=6的元素移至头部：

1. 分裂原树为：
   • A：[1,4]（前2个元素）
   • B：[34,67,2,3]（第3到6个元素）
   • C：[15,78]（第7到8个元素）
2. 合并顺序：merge(B, merge(A, C))，最终得到目标数组：[34,67,2,3,1,4,15,78]

注意事项 #

• 这类结构通常需要手动实现（或依赖语言的扩展库）：C++中可通过policy-based data structures的order_statistics_tree结合自定义分裂合并逻辑实现；Java、Go等语言则需要自行扩展平衡二叉树。
• 块状链表虽能平衡操作时间，但复杂度为O(√n)，不满足对数时间要求，因此不在推荐范围内。

内容的提问来源于stack exchange，提问作者Tychus Findlay