平衡树之splay

(Updated: )
(3 mins to read)

伸展树的核心操作就是splay了，将每次访问的点splay到根节点（类似输入法，频繁打的词会比较靠前）。而正确的splay操作可以保证在将x旋转到根节点的过程中，沿途的所有父节点的深度都会至少减少一半，这种自我调整的特性保证了splay树在各种操作下均摊$O(\log n)$rotate需要分3种情况，splay需要分6种情况比较麻烦，不再赘述（ 其实是不会 ），只给出代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void rotate(int x)
{
  int y = fa[x], z = fa[y], k = rs(x), w = ch[x][k^1];
  ch[y][k] = w; fa[w] = y;
  ch[z][rs(y)] = x; fa[x] = z;
  ch[x][k^1] = y; fa[y] = x;
  up(y); up(x);
}
void splay(int x, int g=0)
{
  while(fa[x]!=g)
  {
    int y = fa[x];
    if(fa[y]!=g) (rs(x)==rs(y) ? rotate(y) : rotate(x));
    rotate(x);
  }
  if(!g) rt = x;
}

splay(x,g)表示将x旋转到g的儿子处，当g=0时即将x旋转到根。用splay来维护权值大小我觉得很麻烦，码量和常数都比较大，一般情况下用pbds或者fhqtreap替代即可。但是用splay来维护区间还是需要只要的。做法也很简单，如果要维护[l,r]，先把l-1旋转到根，再把r+1旋转到l-1的儿子，那么此时r+1的左子树就是要操作的[l,r]部分，直接对这个根节点打上相应的标记即可：

1
2
3
4
5
6
int split(int l, int r)
{
  int x = kth(rt, l-1), y = kth(rt, r+1);
  splay(x); splay(y, x);
  return ch[y][0];
}

pushdown操作只需要在kth函数中进行即可：

1
2
3
4
5
6
7
int kth(int p, int k)
{
  down(p);
  if(ch[p][0]&&sz[ch[p][0]]>=k) return kth(ch[p][0], k);
  else if(sz[ch[p][0]]+1==k) return p;
  else return kth(ch[p][1], k-sz[ch[p][0]]-1);
}

而pushup操作在每次进行split区间操作后都要执行，假设split返回的节点是x，那么就要pushup(y)以及pushup(fa[y])：

1
2
3
4
5
6
void replace(int l, int r, int v)
{
  int x = split(l, r), y = fa[x];
  setv(x, v);
  up(y); up(fa[y]);
}

其实splay的所有操作都可以用fhqtreap来替代，不过在区间操作中要找到区间下标x的点这一功能还是splay方便，只需要把这个点splay到根就可以了，而treap则需要额外维护父亲，而自下而上找。当然splay无可替代的地方就是LCT了，如果用treap就会多一个log。