在前面代码的基础上，我增加一些操作！

1. /* 
2.  * splayModel.cpp 
3.  *   本程序是在从网上搜索到的源代码经过理解、分析过后，在原有功能的基础上， 
4.  *   进行一定的优化及功能的添加，将作为我自己关于 伸展树（SplayTree）的模板 
5.  *   代码。由于能力有限，本程序只处理整数 
6.  *      其实现的功能有： 
7.  *      1、根据整型数组初始化一棵树：init_tree(); 
8.  *      2、往树中插入一个元素：insert(); 
9.  *      3、删除树中的一个元素：remove(); 
10.  *      4、指定区间的元素同时增加某个值：add(); 
11.  *      5、翻转指定区间：reverse(); 
12.  *      6、查询区间的最小值：query(); 
13.  *      7、旋转区间k次：revolve(); 
14.  *      8、插入K个元素到指定元素后面：insert_k(); 
15.  *      9、从树中删除K个元素：remove_k(); 
16.  *  Created on: 2012-10-19 
17.  *      Author: xiaoshuai 
18.  */ 
19. #include <iostream> 
20.  #include <cstdio> 
21.  #include <cstring> 
22.  #include <cstdlib> 
23.  #include <cmath> 
24.  #define INF ~0u>>1 
25.  #define NIL SPLAY 
26.  #define MN 200005 
27.  using namespace std; 
28.  int n,m,l,r,x,pos; 
29.  char s[10]; 
30.  struct SPLAYTREE{ 
31.      struct Node{ 
32.          int key,minv,size,add; 
33.          bool rev; 
34.          Node *left,*right,*father; 
35.          Node (){} 
36.          Node(int _key):key(_key){minv=_key,size=1,add=0,rev=false;} 
37.      }SPLAY[MN],*SP,*root,*head,*tail; 
38. //tail.size=1,head.size=1(初始)而且保证以后接入的结点：Node.size>=head.size 
39.     /* 
40.      * 初始化一棵伸展树，只有head和tail结点 
41.      */ 
42.      void init(){ 
43.          SP=NIL; 
44.          NIL->key=NIL->minv=INF,NIL->size=0;NIL->rev=false;NIL->add=0; 
45.          NIL->left=NIL->right=NIL->father=NIL; 
46.          head=new(++SP)Node(INF); 
47.          head->left=head->right=head->father=NIL; 
48.          tail=new(++SP)Node(INF); 
49.          tail->left=tail->right=tail->father=NIL; 
50.          head->right=tail,tail->father=head,head->size++; 
51.          root=head;//最开始，root的值为head，但接下来就未必了，也就是说：head和tail是固定不变的，而root的指向的地址是会变化的 
52.      } 
53.      /* 
54.       * 懒操作的经典代码：把当前的标记下推一个节点 
55.       * */ 
56.      void pushdown(Node *&t){ 
57.          if(t->rev){
    //如果区间需要旋转 
58.              swap(t->left,t->right); 
59.              t->left->rev=!t->left->rev; 
60.              t->right->rev=!t->right->rev; 
61.              t->rev=false; 
62.          } 
63.          if(t->add){
    //如果区间的值要加add 
64.              if(t->left!=NIL){ 
65.                  t->left->key+=t->add; 
66.                  t->left->minv+=t->add; 
67.                  t->left->add+=t->add; 
68.              } 
69.              if(t->right!=NIL){ 
70.                  t->right->key+=t->add; 
71.                  t->right->minv+=t->add; 
72.                  t->right->add+=t->add; 
73.              } 
74.              t->add=0; 
75.          } 
76.      } 
77.      /* 
78.      *更新区间的最小值和区间元素的个数 
79.      */ 
80.      void update(Node *&t){ 
81.          t->size=t->left->size+t->right->size+1; 
82.          t->minv=min(t->key,min(t->left->minv,t->right->minv)); 
83.      } 
84.     /* 
85.      * 右旋转操作 
86.      * */ 
87.      void zig(Node *&t){ 
88.          Node *f=t->father,*r=t->right; 
89.          pushdown(f->right); 
90.          pushdown(t->left); 
91.          pushdown(t->right); 
92.          t->father=f->father; 
93.          if(f==root) root=t; 
94.          else{ 
95.              if(f->father->left==f) f->father->left=t; 
96.              else f->father->right=t; 
97.          } 
98.          t->right=f,r->father=f,f->father=t,f->left=r; 
99.          update(f);update(t); 
100.      } 
101.      /* 
102.       * 左旋转操作 
103.       * */ 
104.      void zag(Node *&t){ 
105.          Node *f=t->father,*l=t->left; 
106.          pushdown(f->left); 
107.          pushdown(t->left); 
108.          pushdown(t->right); 
109.          t->father=f->father; 
110.          if(f==root) root=t; 
111.          else{ 
112.              if(f->father->left==f) f->father->left=t; 
113.              else f->father->right=t; 
114.          } 
115.          t->left=f,l->father=f,f->father=t,f->right=l; 
116.          update(f);update(t); 
117.      } 
118.      /* 
119.       * 伸展树的核心：伸展操作 
120.       * */ 
121.      void splay(Node *&root,Node *&t){ 
122.          pushdown(t); 
123.          while(root!=t){ 
124.              if(t->father==root){ 
125.                  if(t->father->left==t) zig(t); 
126.                  else zag(t);//单旋转 
127.              } 
128.              else{ 
129.                  if(t->father->father->left==t->father){ 
130.                      if(t->father->left==t) zig(t->father),zig(t);//一字旋转 
131.                      else zag(t),zig(t);//之字旋转 
132.                  }else{ 
133.                      if(t->father->left==t) zig(t),zag(t);//之字旋转 
134.                      else zag(t->father),zag(t);//一字旋转 
135.                  } 
136.              } 
137.          } 
138.      } 
139.      /* 
140.       * 仿线段树建树方式建立一个splay树，与build_tree合用 
141.       * */ 
142.      Node* build(Node *father,int *a,int ll,int rr){ 
143.          if(ll>rr)return NIL; 
144.          int mid=(ll+rr)>>1; 
145.          SP=SP+mid; 
146.          Node *t; 
147.          t=new(SP)Node(a[mid]); 
148.          t->father=father; 
149.          t->left=build(t,a,ll,mid-1); 
150.          t->right=build(t,a,mid+1,rr); 
151.          update(t); 
152.          return t; 
153.      } 
154.      /* 
155.       * function: 把数组a建立成一棵伸展树。采用的建树方式与线段树的建树方式相同 
156.       * 
157.       * @param:root 新建立树的根 
158.       * @param: a  建树用到的数组，0位置不存元素 
159.       * @param: n  数组a中元素的个数 
160.       * */ 
161.      void build_tree(Node *&t,int *a,int n){ 
162.          int ll=1,rr=n; 
163.          int mid=(ll+rr)>>1; 
164.          SP=SP+mid; 
165.          t=new(SP)Node(a[mid]); 
166.          t->father=NIL; 
167.          t->left=build(t,a,ll,mid-1); 
168.          t->right=build(t,a,mid+1,rr); 
169.          update(t); 
170.      } 
171. /* 
172.  * 插入一个值到指定的位置 
173.  * */ 
174.      void insert(int key,int pos){ 
175.          Node *t=new(++SP)Node(key); 
176.          t->left=t->right=t->father=NIL; 
177.          Node *r=root,*p; 
178.          bool flag=false;//默认插入树的左孩子上 
179.          while(pushdown(r),r!=NIL){ 
180.              p=r,r->size++; 
181.              if(r->left->size+1>pos)r=r->left,flag=false; 
182.              else pos-=r->left->size+1,r=r->right,flag=true; 
183.          } 
184.          if(flag) p->right=t; 
185.          else p->left=t; 
186.          t->father=p; 
187.          splay(root,t); 
188.      } 
189.      /* 
190.       * 把pos位置的元素旋转到根结点 
191.       * */ 
192.      void select(Node *&root,int pos){ 
193.          Node *r=root; 
194.          while(pushdown(r),r->left->size+1!=pos){ 
195.              if(r->left->size+1>pos) r=r->left; 
196.              else pos-=r->left->size+1,r=r->right; 
197.          } 
198.          splay(root,r); 
199.      } 
200.      /* 
201.           * 把a中的n个数插入数组中，a的0号位不用 
202.           * */ 
203.      void insert_k(int pos,int *a,int n){ 
204.          Node *t; 
205.          build_tree(t,a,n); 
206.          select(root,pos); 
207.          select(root->right,1); 
208.          root->right->left=t; 
209.          t->father=root->right; 
210.          update(root->right); 
211.          update(root); 
212.          splay(root,t); 
213.      } 
214.      /* 
215.       * 把pos位置的元素删除 
216.       * */ 
217.      void remove(int pos){ 
218.          select(root,pos); 
219.          if(root->left==NIL) root=root->right; 
220.          else if(root->right==NIL) root=root->left; 
221.          else{ 
222.              select(root->left,root->left->size); 
223.              root->left->right=root->right; 
224.              root->right->father=root->left; 
225.              root=root->left; 
226.          } 
227.          root->father=NIL; 
228.          update(root); 
229.      } 
230.      /* 
231.       * 删除区间[l,r] 
232.       * */ 
233.       void remove_k(int ll,int rr){ 
234.           //确定区间 
235.           select(root,ll); 
236.           select(root->right,rr-ll); 
237.           //执行删除操作 
238.           root->right->left=NIL; 
239.           update(root->right); 
240.           update(root); 
241.       } 
242.     /* 
243.      * 区间[l,r]同时加上a 
244.      * */ 
245.      void plus(int l,int r,int a){ 
246.          //确定区间 
247.          select(root,l); 
248.          select(root->right,r-l); 
249.          //执行操作 
250.          Node *t=root->right->left; 
251.          t->add+=a,t->key+=a,t->minv+=a; 
252.          splay(root,t); 
253.      } 
254.      /* 
255.       * 翻转区间[l,r] 
256.       * */ 
257.      void reverse(int l,int r){ 
258.          select(root,l); 
259.          select(root->right,r-l); 
260.          Node *t=root->right->left; 
261.          t->rev=!t->rev; 
262.          splay(root,t); 
263.      } 
264.      /* 
265.        * 旋转转区间[l,r] a次 
266.        * */ 
267.      void revolve(int l,int r,int a){ 
268.          select(root,l); 
269.          select(root->right,r-l); 
270.          select(root->right->left,root->right->left->size-a); 
271.          select(root->right->left->right,root->right->left->right->size); 
272.          Node *p=root->right->left,*t=root->right->left->right; 
273.          p->right=NIL; 
274.          p->father->left=t,t->father=p->father; 
275.          t->right=p,p->father=t; 
276.          update(t);update(p); 
277.          splay(root,p); 
278.      } 
279.      /* 
280.       * 查询区间的最小值 
281.       * */ 
282.      int query(int l,int r){ 
283.          select(root,l); 
284.          select(root->right,r-l); 
285.          return root->right->left->minv; 
286.      } 
287.      /* 
288.       * 从结点t开始 中序遍历树 
289.       * */ 
290.      void inorder(Node *t){ 
291.          pushdown(t); 
292.         if(t->left!=NIL) 
293.             inorder(t->left); 
294.         if(t->key!=INF)printf("%d ",t->key); 
295.         if(t->right!=NIL) 
296.             inorder(t->right); 
297.  
298.     } 
299.  }tree; 
300.  
301.  int main(){ 
302.      int a[10]={0,1,2,3,4,5,6,7,8,9};//a[0]位置不用 
303.      tree.init();//初始化一棵树 
304.      tree.insert_k(1,a,9); 
305.      cout<<"after insert array a after position 0:";tree.inorder(tree.root);cout<<endl; 
306.      tree.insert_k(1,a,9); 
307.      cout<<"after insert array a after position 0:";tree.inorder(tree.root);cout<<endl; 
308.      tree.remove_k(1,11);//确定区间的时候 由于 增加了head和tail两个结点，故需要把r+2，即如果删除[1,9],则参数就为[1,11] 
309.      cout<<"after remove interval [1,9]:"; tree.inorder(tree.root);cout<<endl; 
310.      tree.insert(19,1); 
311.      cout<<"after insert 19 at position 0:"; tree.inorder(tree.root);cout<<endl; 
312.      tree.remove(2);//由于我们查找的时候，左边永远有一个head，故需要加1,即如果我们删除1号位置元素，则参数就为2 
313.      cout<<"after remove position 1:";tree.inorder(tree.root);cout<<endl; 
314.      tree.plus(1,11,10); 
315.      cout<<"after plus 10 between interval [1,9]:"; tree.inorder(tree.root);cout<<endl; 
316.      tree.reverse(1,11); 
317.      cout<<"after reverse interval [1,9]:"; tree.inorder(tree.root);cout<<endl; 
318.      tree.revolve(1,11,3); 
319.      cout<<"after revolve interval [1,9] 3 times:"; tree.inorder(tree.root);cout<<endl; 
320.      int ans=tree.query(1,11); 
321.      cout<<"the min value between interval [1,9] is:"<<ans<<endl; 
322.      return 0; 
323.  }