一：什么是splay（伸展树）
首先了解二叉排序树
伸展树是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
二：如何实现（以下为转载）
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右旋后再左旋。
1588: [HNOI2002]营业额统计
Time Limit:
5 Sec
Memory Limit:
162 MB
Submit:
16618
Solved:
6669
[
Submit
][
Status
][
Discuss
]
Description
营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 输入输出要求
Input
Output
输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
Sample Input
6
5
1
2
5
4
6
Sample Output
12
每次插入后查找当前数的前驱和后继。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxm = 100005;
struct node
{
int left, right, fa;
long long val;
}tr[maxm];
int cnt = 0, root, flag, sum = 0;
void work(int v);
void insert(int v, int k);
int find_1(int v, int k);
int find_2(int v, int k);
void splay(int k);
void leftrotate(int k);
void rightrotate(int k);
int main()
{
int n, i, j, k;
scanf("%d", &n);
scanf("%d", &k);
tr[++cnt].val = k;
tr[cnt].left = tr[cnt].right = tr[cnt].fa = -1;
root = cnt;sum += k;
for (i = 1;i < n;i++)
{
k = 0;
scanf("%d", &k);
work(k);
}
printf("%d\n", sum);
return 0;
}
void work(int v)
{
int a, b;
long long ans;
ans = 10000000000000;
flag = 0, cnt++;
insert(v, root);
if (flag) return;
splay(cnt);
a = find_1(v, root), b = find_2(v, root);
if (a!=-1) ans = min(ans, abs(tr[a].val - v));
if (b!=-1) ans = min(ans, abs(tr[b].val - v));
sum += ans;
}
void insert(int v,int k)
{
if (v == tr[k].val)
{ flag = 1;splay(k); return; }
if (v < tr[k].val)
{
if (tr[k].left == -1)
{
tr[k].left = cnt, tr[cnt].left = tr[cnt].right = -1;
tr[cnt].fa = k, tr[cnt].val = v;
}
else insert(v, tr[k].left);
}
else
{
if (tr[k].right == -1)
{
tr[k].right = cnt, tr[cnt].left = tr[cnt].right = -1;
tr[cnt].fa = k, tr[cnt].val = v;
}
else insert(v, tr[k].right);
}
}
void splay(int k)
{
while (tr[k].fa != -1)
{
int y = tr[k].fa, z = tr[y].fa;
if (z == -1)
{
if (tr[y].left == k) rightrotate(k);
else leftrotate(k);
}
else
{
if (tr[z].left == y&&tr[y].left == k) { rightrotate(y), rightrotate(k); }
if (tr[z].left == y&&tr[y].right == k) { leftrotate(k), rightrotate(k); }
if (tr[z].right == y&&tr[y].right == k) { leftrotate(y), leftrotate(k); }
if (tr[z].right == y&&tr[y].left == k) { rightrotate(k), leftrotate(k); }
}
}
root = k;
}
void leftrotate(int k)
{
int y = tr[k].fa, z = tr[y].fa;
tr[k].fa = z;
if (z != -1)
{
if (tr[z].left == y) tr[z].left = k;
else tr[z].right = k;
}
tr[y].right = tr[k].left;
if (tr[k].left != -1) tr[tr[k].left].fa = y;
tr[k].left = y, tr[y].fa = k;
}
void rightrotate(int k)
{
int y = tr[k].fa, z = tr[y].fa;
tr[k].fa = z;
if (z != -1)
{
if (tr[z].left == y) tr[z].left = k;
else tr[z].right = k;
}
tr[y].left = tr[k].right;
if (tr[k].right != -1) tr[tr[k].right].fa = y;
tr[k].right = y, tr[y].fa = k;
}
int find_1(int v,int k)
{
if (tr[k].left == -1) return -1;
int ans = tr[k].left;
while (tr[ans].right != -1) ans = tr[ans].right;
return ans;
}
int find_2(int v, int k)
{
if (tr[k].right == -1) return -1;
int ans = tr[k].right;
while (tr[ans].left != -1) ans = tr[ans].left;
return ans;
}