今天真是有紀念意義啊……
以前試著捉了N遍的cashier今天竟然AC了，本沙茶終于掌握了平衡樹?。。?br />
【Splay Tree及其實現】
<1>結點記錄的信息：
一般情況下Splay Tree是用線性存儲器（結構數組）來存儲的，可以避免在Linux下的指針異常問題。
這樣對于某個結點，至少要記錄以下的域：值（又叫關鍵字）、左子結點的下標、右子結點的下標、父結點下標、子樹大小（就是以這個結點為根的子樹中結點的總數）以及左右標志（為一個bool值，表示該結點是其父結點的左子結點還是右子結點），所要記錄的其它域根據題目要求而定。另外還有一個域：重復次數mul，就是整棵樹中與這個結點值相同的結點總數（關于這個域的作用將在下一篇里面總結）。
struct node {
int v, c[2], p, sz, mul;
bool d;
} T[MAXN];
以上v為值、c[0]和c[1]表示左右子結點下標、p表示父結點下標、sz表示子樹大小、mul表示重復次數、d表示左右標志。
另外，為了防止越界，將T[0]預留出來作為哨兵結點。在樹中，根結點的p值和葉結點的c值均為0。這個T[0]的sz值必須是0，其余的域無意義。
<2>旋轉操作和伸展操作：
右旋（ZIG）：如果某個非根結點X是其父結點Y的左子結點，則可以通過右旋操作將X旋轉到Y的位置，即：先將Y的左子結點設為X的右子結點，再將X的右子結點設為Y；
左旋（ZAG）：如果某個非根結點X是其父結點Y的右子結點，則可以通過左旋操作將X旋轉到Y的位置，即：先將Y的右子結點設為X的左子結點，再將X的左子結點設為Y；
ZIG和ZAG操作可以合并，稱為rot，代碼如下：
void rot(int x)
{
int y = T[x].p, d = T[x].d;
if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
sc(y, T[x].c[!d], d); sc(x, y, !d); upd(y);
}
其中的sc是set child的縮寫，sc(_p, _c, _d)表示將T[_p]的_d子結點（0：左；1：右。下同）置為_c，代碼如下（_c也可以是0，表示刪除T[_p]對應的子結點）：
void sc(int _p, int _c, bool _d)
{
T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
其中的upd是update的縮寫，upd(x)表示當x的子結點改變時，更新x的一些可維護域（這里只有sz值，有的題目比如NOI2005 sequence里面有其它的可維護域）：
void upd(int x)
{
T[x].sz = T[T[x].c[0]].sz + T[T[x].c[1]].sz + T[x].mul;
}
然后就是Splay Tree的核心操作——伸展操作(Splay)：
Splay(x, r)表示將x伸展到r的子結點處，若r=0，則表示伸展到根（因為根的父結點為T[0]）。過程如下：
（1）設x的父結點為p。若p的父結點即是r，則rot(x)；
（2）若p的父結點不是r且T[x].d=T[p].d，則先rot(p)再rot(x)；
（3）若p的父結點不是r且T[x].d!=T[p].d，則兩次rot(x)；
（4）重復以上過程直到x的父結點為r；
void splay(int x, int r)
{
int p; while ((p = T[x].p) != r) if (T[p].p == r) rot(x); else if (T[x].d == T[p].d) {rot(p); rot(x);} else {rot(x); rot(x);} upd(x);
}
這里有一個問題：為什么在旋轉操作中只更新y不更新x，而在伸展操作的最后則要更新x？這個在JZP神犇的論文中有解釋：因為在旋轉過程中，x的子結點一直在改變，故過早地跟新x沒有意義。
<3>查找操作：
下面開始進入正式操作了。
首先是查找。find(x)表示在樹中找值為x的結點，若找到返回其下標，若找不到返回0。這個應該是很容易實現的。
int find(int x)
{
int i = x, v0; while (i) {v0 = T[i].v; if (v0 == x) break; else i = T[i].c[v0 > x];} return i;
}
<4>插入操作：
ins(_v)表示在樹中插入一個值為_v的結點。由于樹是否為空的問題以及mul的引入，插入操作有三種可能結果：
（1）樹為空（根結點為0）：此時將插入一個新的結點，值為_v，初始sz、mul值均為1，并將其作為根結點；
（2）樹非空且值為_v的結點在樹中不存在：此時將插入一個新的結點，值為_v，初始sz、mul值均為1；
（3）樹非空且值為_v的結點在樹中已存在：此時會將樹中這個值為_v的結點的mul值加1；
void ins(int _v)
{
if (!root) {T[++n].v = _v; T[n].c[0] = T[n].c[1] = T[n].p = 0; T[n].sz = T[n].mul = 1; root = n; return;}
int i = root, j;
while (1) {
T[i].sz++;
if (T[i].v == _v) {T[i].mul++; splay(i, 0); return;}
j = T[i].c[_v > T[i].v];
if (!j) break; else i = j;
}
T[++n].v = _v; T[n].c[0] = T[n].c[1] = 0; T[n].sz = T[n].mul = 1; sc(i, n, _v > T[i].v); splay(n, 0);
}
<5>刪除操作：
del(x)表示將下標為x的結點刪除。
除了一般的二叉查找樹的刪除方法外，Splay Tree還有一種刪除方式：先找到x的前趨P和x的后繼S（具體操作見<6>），并將P伸展到根，S伸展到P的右子結點處，這樣S的左子樹中只有一個結點，就是x，然后再將S的左子結點置為0即可。需要注意的是幾種特殊情況：
（1）x無前趨或無后繼：此時將x伸展到根后，x只有一棵子樹，直接將根結點設為x的那個子結點即可；
（2）x既無前趨也無后繼：此時x就是樹中的唯一一個結點，將根結點設為0即可；
（3）T[x].mul>1，直接將T[x].mul值減1（與插入類似）；
void del(int x)
{
if (T[x].mul > 1) T[x].mul--; else {
splay(x, 0);
int y = succ(), y2 = pred();
if (!y) {root = T[x].c[0]; T[root].p = 0;} else if (!y2) {root = T[x].c[1]; T[root].p = 0;} else {
splay(y2, 0); splay(y, root);
T[x].p = 0; T[y].c[T[x].d] = 0; upd(y); upd(root);
}
}
}
<6>找前趨和后繼：
pred(x)和succ(x)：分別求出x的前趨和后繼（x的前趨表示樹中值小于x的最大的結點；x的后繼表示樹中值大于x的最小的結點），并返回它們的下標，若不存在返回0。
先將x伸展到根，然后x的左子結點的右鏈上的最后一個結點就是x的前趨，x的右子結點的左鏈上的最后一個結點就是x的后繼。
int pred()
{
int i = T[root].c[0], j;
if (!i) return 0;
while (j = T[i].c[1]) i = j;
return i;
}
int succ()
{
int i = T[root].c[1], j;
if (!i) return 0;
while (j = T[i].c[0]) i = j;
return i;
}
注意，這里的pred和succ是求根結點的前趨和后繼，因此在調用pred或succ前必須保證結點x已經被伸展到了根的位置。
前趨和后繼還有另一種定義方式：x的前趨表示樹中值不大于x的最大的結點，x的后繼表示樹中值不小于x的最小的結點，此時只需在pred和succ函數的開頭分別加入if (T[root].mul > 1) return root;即可。
<7>找第K小以及找指定結點是第幾?。?br />找第K小以及找指定結點是第幾小的操作是平衡樹的特有操作。Splay Tree找第K小的操作與其它平衡樹相同。
int Find_Kth(int K)
{
int i = root, s0, m0;
while (1) {
s0 = T[T[i].c[0]].sz; m0 = T[i].mul;
if (K <= s0) i = T[i].c[0]; else if (K <= s0 + m0) return T[i].v; else {K -= s0 + m0; i = T[i].c[1];}
}
}
而Splay Tree找指定結點是第幾小的操作則是特有的：將這個結點伸展到根，則其(左子樹大小+1)即為結果。
int rank(int x)
{
splay(x, 0); return T[T[x].c[0]].sz + 1;
}
【例題】
NOI2004 cashier：
本題中涉及到一個進階操作：刪除值在某一區間內的所有結點。這一操作會在下一篇里總結。
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 100001, INF = ~0U >> 2;
struct node {
int v, c[2], p, sz, mul;
bool d;
} T[MAXN];
int n = 0, root, res, tot = 0;
void upd(int x)
{
T[x].sz = T[T[x].c[0]].sz + T[T[x].c[1]].sz + T[x].mul;
}
void sc(int _p, int _c, bool _d)
{
T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
void rot(int x)
{
int y = T[x].p, d = T[x].d;
if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
sc(y, T[x].c[!d], d); sc(x, y, !d); upd(y); upd(x);
}
void splay(int x, int r)
{
int i = x, p, p0;
while ((p0 = T[i].p) != r) {
p = T[p0].p;
if (p == r) rot(i); else if (T[i].d == T[p0].d) {rot(p0); rot(i);} else {rot(i); rot(i);}
}
}
void ins(int _v)
{
if (!root) {T[++n].v = _v; T[n].c[0] = T[n].c[1] = T[n].p = 0; T[n].sz = T[n].mul = 1; root = n; return;}
int i = root, j;
while (1) {
T[i].sz++;
if (T[i].v == _v) {T[i].mul++; splay(i, 0); return;}
j = T[i].c[_v > T[i].v];
if (!j) break; else i = j;
}
T[++n].v = _v; T[n].c[0] = T[n].c[1] = 0; T[n].sz = T[n].mul = 1; sc(i, n, _v > T[i].v); splay(n, 0);
}
void del(int lmt)
{
if (!root) return;
int i = root, _min = INF, b = 0, v0;
while (i) {
v0 = T[i].v;
if (v0 == lmt) {b = i; break;}
if (v0 < lmt) i = T[i].c[1]; else {if (v0 < _min) {_min = v0; b = i;} i = T[i].c[0];}
}
if (!b) {tot += T[root].sz; root = 0;} else {splay(b, 0); tot += T[T[root].c[0]].sz; T[T[root].c[0]].p = 0; T[root].c[0] = 0; upd(root);}
}
int Find_Kth(int K)
{
int i = root, s0, m0;
while (1) {
s0 = T[T[i].c[0]].sz; m0 = T[i].mul;
if (K <= s0) i = T[i].c[0]; else if (K <= s0 + m0) return T[i].v; else {K -= s0 + m0; i = T[i].c[1];}
}
}
int main()
{
freopen("cashier.in", "r", stdin);
freopen("cashier.out", "w", stdout);
int m, minv, delt = 0, x;
char ch;
scanf("%d%d%*c", &m, &minv);
re(i, m) {
scanf("%c%d%*c", &ch, &x);
switch(ch) {
case 'I': {if (x >= minv) ins(x - delt); break;}
case 'A': {delt += x; break;}
case 'S': {delt -= x; del(minv - delt); break;}
case 'F': if (T[root].sz - x + 1 <= 0) printf("%d\n", -1); else printf("%d\n", Find_Kth(T[root].sz - x + 1) + delt);
}
}
printf("%d\n", tot);
fclose(stdin); fclose(stdout);
return 0;
}
【相關論文】
（1）
The Magical Splay（2）
運用伸展樹解決數列維護問題【感謝】
CLJ 神犇
GYZ 神犇
Jollwish 神犇
以及網上提供cashier標程的
etc.