介绍
Spaly是伸展树 也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的
处理问题
伸展树在区间插入，区间删除，区间翻转，区间旋转的问题中应用较多。
参考
入门解析: https://www.cnblogs.com/cjyyb/p/7499020.html
操作介绍:https://blog.csdn.net/niuox/article/details/8018280
模板参考:https://www.cnblogs.com/Mathics/p/3971220.html
各种树: https://blog.csdn.net/MetalSeed/article/details/11846255
学习
常用模板
1. 处理序列区间问题，以下标来建树
未测试，未写完，待续... 2018.08.03 21:25
insert(l,r,v) del(l,r)未测试，其他测试题为POJ 3580 POJ 3468 2018.08.05 21:45 自己有点懒了，好几天了...， 未写完，待续... 2018.08.05 21:25
insert del 已测试 测试题目 bzoj 1269 其中insert(l,r) del(l,r) sum和 和minn未找到测试题，理论不错... 2018.08.06 15:52 未完待续...
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define rd(a) scanf("%d",&a)
#define rld(a) scanf("%lld",&a)
#define rs(a) scanf("%s",a)
#define me(a,b) memset(a,b,sizeof(a))
const ll maxn=3e5+10;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;/***** 板子开始 ******/
int a[maxn];
int f[maxn];
int ch[maxn][2];
ll sum[maxn];
int val[maxn];
int lazy[maxn];
int size[maxn];
bool flip[maxn];
int minn[maxn];
int root;
int cnt=0;
int n;
struct SplayTree{inline void pushUp(int u){ //yessize[u]=size[ch[u][0]]+size[ch[u][1]]+1;sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u]+lazy[u];minn[u]=val[u];if(ch[u][0]) minn[u]=min(minn[u],minn[ch[u][0]]);if(ch[u][1]) minn[u]=min(minn[u],minn[ch[u][1]]);}inline void pushDown(int u){ //yesif(flip[u]){flip[ch[u][0]]^=1;flip[ch[u][1]]^=1;swap(ch[u][1],ch[u][0]);flip[u]=0;}if(lazy[u]){if(ch[u][0]) {lazy[ch[u][0]]+=lazy[u]; sum[ch[u][0]]+=(ll)lazy[u]*size[ch[u][0]];minn[ch[u][0]]+=lazy[u]; }if(ch[u][1]) {lazy[ch[u][1]]+=lazy[u];sum[ch[u][1]]+=(ll)lazy[u]*size[ch[u][1]];minn[ch[u][1]]+=lazy[u]; }val[u]+=lazy[u];lazy[u]=0;}}inline void addNode(int &u,int fa,int v){ //yesu=++cnt;f[u]=fa;ch[u][1]=ch[u][0]=0;flip[u]=false;lazy[u]=0;val[u]=v;minn[u]=v;sum[u]=v;size[u]=1;}void bulidTree(int l,int r,int &u,int fa,int num[]){ //yesif(l>r) return;int mid=(l+r)>>1;addNode(u,fa,num[mid]);if(l<mid) bulidTree(l,mid-1,ch[u][0],u,num);if(r>mid) bulidTree(mid+1,r,ch[u][1],u,num);pushUp(u);}inline void rotate(int x,int p){ yesint y=f[x];pushDown(y);pushDown(x);ch[y][!p]=ch[x][p];f[ch[x][p]]=y;f[x]=f[y];if(f[y]) ch[f[y]][ch[f[y]][1]==y]=x;f[y]=x;ch[x][p]=y;pushUp(y);}void Splay(int x,int goal) { //goal 为x到根节点路上的点 //yespushDown(x);while(f[x]!=goal){int y=f[x];int z=f[y];pushDown(z);pushDown(y);if(f[y]==goal) rotate(x,ch[y][0]==x);else{int g=(ch[z][0]==y);if(ch[y][g]==x) rotate(x,!g);else rotate(y,g);rotate(x,g);}} pushUp(x);if(goal==0) root=x;} int getPre(int x){ Splay(x,0); int temp=ch[root][0];if(!temp) return 0;pushDown(temp);while(ch[temp][1]) temp=ch[temp][1],pushDown(temp);return temp;}int getNex(int x){ Splay(x,0); int temp=ch[x][1];if(!temp) return 0;pushDown(temp);while(ch[temp][0]) temp=ch[temp][0],pushDown(temp);return temp;}int findx(int x){ yesx++;int r=root;pushDown(r);while(x){ if(size[ch[r][0]]>=x){r=ch[r][0];}else{x-=size[ch[r][0]]+1;if(!x) return r;r=ch[r][1];}pushDown(r);}return r;}inline void xgth(int x,int goal){Splay(findx(x),goal);}inline void insert(int x,int v){ //yesxgth(x-1,0);xgth(x,root);addNode(ch[ch[root][1]][0],ch[root][1],v);pushUp(ch[root][1]);pushUp(root);}inline void insert(int x,int l,int r,int v[]){xgth(x-1,0);xgth(x,root);bulidTree(l,r,ch[ch[root][1]][0],ch[root][1],v);pushUp(ch[root][1]);pushUp(root); }inline ll query_sum(int l,int r){ //yesxgth(l-1,0);xgth(r+1,root);return sum[ch[ch[root][1]][0]]; }inline int query_min(int l,int r){ //yesxgth(l-1,0);xgth(r+1,root);return minn[ch[ch[root][1]][0]];}inline void update(int l,int r,int v){ //yesxgth(l-1,0);xgth(r+1,root);lazy[ch[ch[root][1]][0]]+=v;minn[ch[ch[root][1]][0]]+=v;sum[ch[ch[root][1]][0]]+=(ll)v*size[ch[ch[root][1]][0]];}inline void reversal(int l,int r){ //yesxgth(l-1,0);xgth(r+1,root);flip[ch[ch[root][1]][0]]^=1;}inline void del(int x){ //yesxgth(x-1,0);xgth(x+1,root);ch[ch[root][1]][0]=0;pushUp(ch[root][1]);pushUp(root);}inline void del(int l,int r){xgth(l-1,0);xgth(r+1,root);ch[ch[root][1]][0]=0;pushUp(ch[root][1]);pushUp(root);}inline void print(int r,int v){ //yespushDown(r);if(ch[r][0]) print(ch[r][0],v);if(val[r]) printf("%d%c",val[r],r==v?'\n':' ');if(ch[r][1]) print(ch[r][1],v);}inline void print(){int v=findx(n);print(root,v);}inline void init(){root=cnt=0;addNode(root,0,0);addNode(ch[root][1],root,0);/*输入*/for(int i=0;i<n;i++){a[i]= i+1;}bulidTree(0,n-1,ch[ch[root][1]][0],ch[root][1],a);pushUp(ch[root][1]);pushUp(root);}inline void init_v(){root=cnt=0;addNode(root,0,0);addNode(ch[root][1],root,0);/*输入*/for(int i=0;i<n;i++){rd(a[i);}bulidTree(0,n-1,ch[ch[root][1]][0],ch[root][1],a);pushUp(ch[root][1]);pushUp(root);}};