我根本不会平衡树

RyexAwl · 2024-05-14 15:04:00 · 个人记录

使用无旋 treap 维护权值，需要显示或隐示的保证权值互不相同。对于权值互不相同的 treap，可以看成是随机生成长度为 n 的排列的笛卡尔树（排列的下标看成维护的权值，排列的值看成生成的第二关键字），期望深度 O(\log n)。(无旋平衡树（范浩强 Treap）平均时间复杂度证明 )

例如 P10284 [USACO24OPEN] Splitting Haybales P，这个题就很骚，不加第二关键字扰动 T 飞了。

平衡树合并

参考资料 "Merging treaps" -- or how to merge sorted sets in good complexity...

int merge(int x,int y) {
  if (!x || !y) {
    return x + y;
  }
  if (a[x].dat < a[y].dat) {
    std::swap(x,y);
  }
  pushdown(x);
  int A,B; 
  split(y,a[x].val,A,B);
  a[x].ls = merge(a[x].ls,A);
  a[x].rs = merge(a[x].rs,B);
  return x;
}

设势能 \varphi=\sum \log(a_{i+1}-a_i)。对 A,B 合并的势能变化 \Delta \varphi=\varphi(A)+\varphi(B)-\varphi(A\cup B)。

对于合并 A,B，如果 A,B 之间需要合并 k 个连续段，那么复杂度是 O(k\log n) 的。

有一个结论是：

\Delta \varphi\ge k-O(\log V)

即 k\le \Delta\varphi +O(\log V)。那么 \sum k\le \sum \Delta \varphi + m\log V，其中 m 表示合并次数。

因为任意时刻 \varphi 非负，所以 \sum \Delta \varphi 不超过 \varphi 增加的级别，只要 \varphi 增加不大，那么复杂度就对对了。