014-数据结构-Treap

基于随机优先级的自平衡二叉搜索树 Treap，作为“顺序容器”支持对序列进行对数时间的 split/join，并易于按需扩展维护额外信息。

> Description: A short self-balancing tree. It acts as a > sequential container with log-time splits/joins, and > is easy to augment with additional data. > Time: $O(\log N)$

• 结构与字段（据实现）

  • Node：包含左右子指针 l, r，键值 val，随机优先级 y（构造时 rand()），以及子树大小 c（默认 1）。
  • cnt(Node* n)：空指针返回 0，否则返回 n->c。
  • Node::recalc()：按 c = cnt(l) + cnt(r) + 1 维护子树大小。

• 基本遍历

  • each(Node* n, F f)：中序遍历（左-根-右），对每个结点的 val 调用回调 f。

• 核心操作（顺序容器语义）

  • split(Node* n, int k)：
    • 按“前 k 个元素”将树分为两棵（返回 {L, R}）。
    • 若左子树大小 cnt(n->l) >= k，则在左子树递归 split，并将结果右部接回 n->l；否则在右子树以 k - cnt(n->l) - 1 递归并将结果左部接回 n->r。
    • 每次结构变动后调用 recalc() 维护 c。
  • merge(Node* l, Node* r)：
    • 按随机优先级 y 合并两棵 Treap，较大 y 的结点为根；相应地递归合并其子树并 recalc()。
  • ins(Node* t, Node* n, int pos)：
    • 先 split(t, pos)，再将新结点 n 插入到中间：merge( merge(l, n), r )。

• 示例操作

  • move(Node*& t, int l, int r, int k)：
    • 将区间 [l, r) 从原位置移动到索引 k：
      1. split(t, l) 得到 a 与余部；再 split(余部, r-l) 得到区间段 b 与余下 c；
      2. 若 k <= l：t = merge( ins(a, b, k), c )；否则：t = merge( a, ins(c, b, k - r) )。

• 复杂度

  • split/merge/ins 等核心操作均为期望 O(log N)。

关联节点

• 010-数据结构-顺序统计树
• 012-数据结构-线段树
• 003-数据结构-树状数组