【数据结构】伸展树 Splay Tree
Splay Tree
类别：二叉排序树空间效率：O(n)
时间效率：O(log n)内完成插入、查找、删除操作创造者：Daniel Sleator和Robert Tarjan优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。
注：所有图片来自wiki。
http://blog.csdn.net/cyberzhg/article/details/8058208
Tree Rotation
树的旋转是splay的基础，对于二叉查找树来说，树的旋转不破坏查找树的结构。
Splaying
Splaying是Splay Tree中的基本操作，为了让被查询的条目更接近树根，Splay Tree使用了树的旋转操作，同时保证二叉排序树的性质不变。Splaying的操作受以下三种因素影响：节点x是父节点p的左孩子还是右孩子节点p是不是根节点，如果不是节点p是父节点g的左孩子还是右孩子同时有三种基本操作：
Zig Step
当p为根节点时，进行zip step操作。当x是p的左孩子时，对x右旋；当x是p的右孩子时，对x左旋。
Zig-Zig Step
当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。当x和p同为左孩子时，依次将p和x右旋；当x和p同为右孩子时，依次将p和x左旋。
Zig-Zag Step
当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。当p为左孩子，x为右孩子时，将x左旋后再右旋。当p为右孩子，x为左孩子时，将x右旋后再左旋。
应用
Splay Tree可以方便的解决一些区间问题，根据不同形状二叉树先序遍历结果不变的特性，可以将区间按顺序建二叉查找树。每次自下而上的一套splay都可以将x移动到根节点的位置，利用这个特性，可以方便的利用Lazy的思想进行区间操作。对于每个节点记录size，代表子树中节点的数目，这样就可以很方便地查找区间中的第k小或第k大元素。对于一段要处理的区间[x, y]，首先splay x-1到root，再splay y+1到root的右孩子，这时root的右孩子的左孩子对应子树就是整个区间。这样，大部分区间问题都可以很方便的解决，操作同样也适用于一个或多个条目的添加或删除，和区间的移动。
POJ2764 Feed the dogshttp://poj.org/problem?id=2764
http://blog.csdn.net/cyberzhg/article/details/8058154
区间不会重叠，所以不可能有首首相同或尾尾相同的情况，读入所有区间，按照右端由小到大排序。然后通过维护splay进行第k小元素的查询操作。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 100005;const int MAXM = 100005;const int INF = 0x7fffffff;class SplayTree{public: SplayTree() { nil.size = 0; nil.value = INF; nil.min = INF; nil.lchild = &nil; nil.rchild = &nil; nil.parent = &nil; } inline void make(int array[], int n) { nodeNumber = 0; int mid = (n - 1) >> 1; root = newNode(&nil, array[mid]); root->lchild = make(0, mid - 1, root, array); root->rchild = make(mid + 1, n - 1, root, array); update(root); } inline void ADD(int x, int y, int D) { find(x, &nil); find(y + 2, root); root->rchild->lchild->lazy += D; } inline void REVERSE(int x, int y) { find(x, &nil); find(y + 2, root); root->rchild->lchild->isReverse ^= true; } inline void REVOLVE(int x, int y, int T) { int len = y - x + 1; T = ((T % len) + len) % len; if(T) { find(y - T + 1, &nil); find(y + 2, root); SplayNode *d = root->rchild->lchild; root->rchild->lchild = &nil; find(x, &nil); find(x + 1, root); root->rchild->lchild = d; d->parent = root->rchild; } } inline void INSERT(int x, int P) { find(x + 1, &nil); find(x + 2, root); root->rchild->lchild = newNode(root->rchild, P); } inline void DELETE(int x) { find(x, &nil); find(x + 2, root); root->rchild->lchild = &nil; } inline void MIN(int x, int y) { find(x, &nil); find(y + 2, root); pushdown(root->rchild->lchild); printf("%d\n", root->rchild->lchild->min); } inline void print() { printf("Splay Linear: \n"); print(root); printf("\n"); } inline void prints() { printf("Splay Structure: \n"); prints(root); printf("\n"); }private: struct SplayNode { int value, size, lazy; SplayNode *parent, *lchild, *rchild; int min; bool isReverse; } nil, node[MAXN + MAXM]; int nodeNumber; SplayNode *root; inline SplayNode *newNode(SplayNode *parent, const int value) { node[nodeNumber].value = value; node[nodeNumber].size = 1; node[nodeNumber].lazy = 0; node[nodeNumber].parent = parent; node[nodeNumber].lchild = &nil; node[nodeNumber].rchild = &nil; node[nodeNumber].min = value; node[nodeNumber].isReverse = false; return &node[nodeNumber++]; } SplayNode *make(int l, int r, SplayNode *parent, int array[]) { if(l > r) { return &nil; } int mid = (l + r) >> 1; SplayNode *x = newNode(parent, array[mid]); x->lchild = make(l, mid - 1, x, array); x->rchild = make(mid + 1, r, x, array); update(x); return x; } inline void update(SplayNode *x) { if(x == &nil) { return; } x->size = x->lchild->size + x->rchild->size + 1; x->min = min(x->value, min(x->lchild->min, x->rchild->min)); } inline void pushdown(SplayNode *x) { if(x == &nil) { return; } if(x->isReverse) { swap(x->lchild, x->rchild); x->lchild->isReverse ^= true; x->rchild->isReverse ^= true; x->isReverse = false; } if(x->lazy) { x->value += x->lazy; x->min += x->lazy; x->lchild->lazy += x->lazy; x->rchild->lazy += x->lazy; x->lazy = 0; } } inline void rotateLeft(SplayNode *x) { SplayNode *p = x->parent; pushdown(x->lchild); pushdown(x->rchild); pushdown(p->lchild); p->rchild = x->lchild; p->rchild->parent = p; x->lchild = p; x->parent = p->parent; if(p->parent->lchild == p) { p->parent->lchild = x; } else { p->parent->rchild = x; } p->parent = x; update(p); update(x); if(root == p) { root = x; } } inline void rotateRight(SplayNode *x) { SplayNode *p = x->parent; pushdown(x->lchild); pushdown(x->rchild); pushdown(p->rchild); p->lchild = x->rchild; p->lchild->parent = p; x->rchild = p; x->parent = p->parent; if(p->parent->lchild == p) { p->parent->lchild = x; } else { p->parent->rchild = x; } p->parent = x; update(p); update(x); if(root == p) { root = x; } } inline void splay(SplayNode *x, SplayNode *y) { pushdown(x); while(x->parent != y) { if(x->parent->parent == y) { if(x->parent->lchild == x) { rotateRight(x); } else { rotateLeft(x); } } else if(x->parent->parent->lchild == x->parent) { if(x->parent->lchild == x) { rotateRight(x->parent); rotateRight(x); } else { rotateLeft(x); rotateRight(x); } } else { if(x->parent->rchild == x) { rotateLeft(x->parent); rotateLeft(x); } else { rotateRight(x); rotateLeft(x); } } } update(x); } inline void find(int k, SplayNode *y) { SplayNode *x = root; pushdown(x); while(k != x->lchild->size + 1) { if(k <= x->lchild->size) { x = x->lchild; } else { k -= x->lchild->size + 1; x = x->rchild; } pushdown(x); } splay(x, y); } inline void print(SplayNode *x) { if(x == &nil) { return; } pushdown(x); print(x->lchild); printf("%d: %d %d %d %d\n", x->value, x->min, x->parent->value, x->lchild->value, x->rchild->value); print(x->rchild); } inline void prints(SplayNode *x) { if(x == &nil) { return; } pushdown(x); if(x->value == INF) { printf("INF : "); } else { printf("%d : ", x->value); } if(x->lchild == &nil) { printf("nil "); } else { if(x->lchild->value == INF) { printf("INF "); } else { printf("%d ", x->lchild->value); } } if(x->rchild == &nil) { printf("nil\n"); } else { if(x->rchild->value == INF) { printf("INF\n"); } else { printf("%d\n", x->rchild->value); } } prints(x->lchild); prints(x->rchild); }} splayTree;char buffer[128];int array[MAXN];int n, m;int main(){ int x, y, D, T, P; scanf("%d", &n); for(int i=1;i<=n;++i) { scanf("%d", &array[i]); } array[0] = INF; array[n+1] = INF; splayTree.make(array, n + 2); scanf("%d", &m); while(m--) { scanf("%s", buffer); switch(buffer[0]) { case 'A': scanf("%d%d%d", &x, &y, &D); splayTree.ADD(x, y, D); break; case 'R': if('E' == buffer[3]) { scanf("%d%d", &x, &y); splayTree.REVERSE(x, y); } else { scanf("%d%d%d", &x, &y, &T); splayTree.REVOLVE(x, y, T); } break; case 'I': scanf("%d%d", &x, &P); splayTree.INSERT(x, P); break; case 'D': scanf("%d", &x); splayTree.DELETE(x); break; case 'M': scanf("%d%d", &x, &y); splayTree.MIN(x, y); break; } } return 0;}
