学习伸展树，个人觉得其实思想其实挺容易懂的：

一、（二八原则）20%的数据是经常操作的，而剩下80%的数据一般都不怎么会管！

二。旋转到根：每插入或者删除一个结点，都把插入的结点（删除结点的孩子）旋转到根。

最难理解的是代码：我自己在网上找了很久，找到我认为比较容易理解的代码，就拿来分析了：（POJ3580）http://www.cnblogs.com/Delostik/archive/2011/07/26/2116991.html

向这位大年致敬，我个人觉得代码写得相当有水平！

1. #include <iostream> 
2.  #include <cstdio> 
3.  #include <cstring> 
4.  #include <cstdlib> 
5.  #include <cmath> 
6.  #define INF ~0u>>1 
7.  #define NIL SPLAY 
8.  #define MN 200005 
9.  using namespace std; 
10.  int n,m,l,r,x,pos; 
11.  char s[10]; 
12.  struct SPLAYTREE{ 
13.      struct NODE{ 
14.          int key,minv,size,add; 
15.          bool rev; 
16.          NODE *left,*right,*father; 
17.          NODE (){} 
18.          NODE(int _key):key(_key){minv=_key,size=1,add=0,rev=false;} 
19.      }SPLAY[MN],*SP,*root,*head,*tail; 
20. //tail.size=1,head.size=1(初始)而且保证以后接入的结点：node.size>=head.size 
21.      void init(){ 
22.          SP=NIL; 
23.          NIL->key=NIL->minv=INF,NIL->size=0;NIL->rev=false;NIL->add=0; 
24.          NIL->left=NIL->right=NIL->father=NIL; 
25.          head=new(++SP)NODE(INF); 
26.          head->left=head->right=head->father=NIL; 
27.          tail=new(++SP)NODE(INF); 
28.          tail->left=tail->right=tail->father=NIL; 
29.          head->right=tail,tail->father=head,head->size++; 
30.          root=head;//最开始，root的值为head，但接下来就未必了，也就是说：head和tail是固定不变的，而root的指向的地址是会变化的 
31.      } 
32.  
33.      void pushdown(NODE *&t){ 
34.          if(t->rev){ 
35.              swap(t->left,t->right); 
36.              t->left->rev=!t->left->rev; 
37.              t->right->rev=!t->right->rev; 
38.              t->rev=false; 
39.          } 
40.          if(t->add){ 
41.              if(t->left!=NIL){ 
42.                  t->left->key+=t->add; 
43.                  t->left->minv+=t->add; 
44.                  t->left->add+=t->add; 
45.              } 
46.              if(t->right!=NIL){ 
47.                  t->right->key+=t->add; 
48.                  t->right->minv+=t->add; 
49.                  t->right->add+=t->add; 
50.              } 
51.              t->add=0; 
52.          } 
53.      } 
54.  
55.      void update(NODE *&t){ 
56.          t->size=t->left->size+t->right->size+1; 
57.          t->minv=min(t->key,min(t->left->minv,t->right->minv)); 
58.      } 
59.  
60.      void zig(NODE *&t){ 
61.          NODE *f=t->father,*r=t->right; 
62.          pushdown(f->right); 
63.          pushdown(t->left); 
64.          pushdown(t->right); 
65.          t->father=f->father; 
66.          if(f==root) root=t; 
67.          else{ 
68.              if(f->father->left==f) f->father->left=t; 
69.              else f->father->right=t; 
70.          } 
71.          t->right=f,r->father=f,f->father=t,f->left=r; 
72.          update(f);update(t); 
73.      } 
74.  
75.      void zag(NODE *&t){ 
76.          NODE *f=t->father,*l=t->left; 
77.          pushdown(f->left); 
78.          pushdown(t->left); 
79.          pushdown(t->right); 
80.          t->father=f->father; 
81.          if(f==root) root=t; 
82.          else{ 
83.              if(f->father->left==f) f->father->left=t; 
84.              else f->father->right=t; 
85.          } 
86.          t->left=f,l->father=f,f->father=t,f->right=l; 
87.          update(f);update(t); 
88.      } 
89.  
90.      void splay(NODE *&root,NODE *&t){ 
91.          pushdown(t); 
92.          while(root!=t){ 
93.              if(t->father==root){ 
94.                  if(t->father->left==t) zig(t); 
95.                  else zag(t); 
96.              } 
97.              else{ 
98.                  if(t->father->father->left==t->father){ 
99.                      if(t->father->left==t) zig(t->father),zig(t); 
100.                      else zag(t),zig(t); 
101.                  }else{ 
102.                      if(t->father->left==t) zig(t),zag(t); 
103.                      else zag(t->father),zag(t); 
104.                  } 
105.              } 
106.          } 
107.      } 
108. /* 
109.  * 这里有很重要的一点：决定伸展树关键字大于的是：size,不是key(value),也不是index 
110.  * */ 
111.      void insert(int key,int pos){ 
112.          NODE *t=new(++SP)NODE(key); 
113.          t->left=t->right=t->father=NIL; 
114.          NODE *r=root,*p; 
115.          bool flag=false;//默认插入树的左孩子上 
116.          while(pushdown(r),r!=NIL){ 
117.              p=r,r->size++; 
118.              if(r->left->size+1>pos)r=r->left,flag=false; 
119.              else pos-=r->left->size+1,r=r->right,flag=true; 
120.          } 
121.          if(flag) p->right=t; 
122.          else p->left=t; 
123.          t->father=p; 
124.          splay(root,t); 
125.      } 
126.  
127.      void select(NODE *&root,int pos){ 
128.          NODE *r=root; 
129.          while(pushdown(r),r->left->size+1!=pos){ 
130.              if(r->left->size+1>pos) r=r->left; 
131.              else pos-=r->left->size+1,r=r->right; 
132.          } 
133.          splay(root,r); 
134.      } 
135.  
136.      void remove(int pos){ 
137.          select(root,pos); 
138.          if(root->left==NIL) root=root->right; 
139.          else if(root->right==NIL) root=root->left; 
140.          else{ 
141.              select(root->left,root->left->size); 
142.              root->left->right=root->right; 
143.              root->right->father=root->left; 
144.              root=root->left; 
145.          } 
146.          root->father=NIL; 
147.          update(root); 
148.      } 
149.  
150.      void plus(int l,int r,int a){ 
151.          select(root,l); 
152.          select(root->right,r-l); 
153.          NODE *t=root->right->left; 
154.          t->add+=a,t->key+=a,t->minv+=a; 
155.          splay(root,t); 
156.      } 
157.  
158.      void reverse(int l,int r){ 
159.          select(root,l); 
160.          select(root->right,r-l); 
161.          NODE *t=root->right->left; 
162.          t->rev=!t->rev; 
163.          splay(root,t); 
164.      } 
165.  
166.      void revolve(int l,int r,int a){ 
167.          select(root,l); 
168.          select(root->right,r-l); 
169.          select(root->right->left,root->right->left->size-a); 
170.          select(root->right->left->right,root->right->left->right->size); 
171.          NODE *p=root->right->left,*t=root->right->left->right; 
172.          p->right=NIL; 
173.          p->father->left=t,t->father=p->father; 
174.          t->right=p,p->father=t; 
175.          update(t);update(p); 
176.          splay(root,p); 
177.      } 
178.  
179.      int query(int l,int r){ 
180.          select(root,l); 
181.          select(root->right,r-l); 
182.          return root->right->left->minv; 
183.      } 
184.  }tree; 
185.  
186.  int main(){ 
187.      tree.init(); 
188.      scanf("%d",&n); 
189.      for(int i=1;i<=n;i++){ 
190.          scanf("%d",&x); 
191.          tree.insert(x,i); 
192.      } 
193.  
194.      scanf("%d",&m);getchar(); 
195.      while(m--){ 
196.          scanf("%s",s); 
197.          switch(s[0]){ 
198.              case 'A': 
199.                  scanf("%d%d%d",&l,&r,&x); 
200.                  tree.plus(l,r+2,x); 
201.                  break; 
202.              case 'I': 
203.                  scanf("%d%d",&pos,&x); 
204.                  tree.insert(x,pos+1); 
205.                  break; 
206.              case 'D': 
207.                  scanf("%d",&pos); 
208.                  tree.remove(pos+1); 
209.                  break; 
210.              case 'M': 
211.                  scanf("%d%d",&l,&r); 
212.                  printf("%d\n",tree.query(l,r+2)); 
213.                  break; 
214.              case 'R': 
215.                  if(s[3]=='E'){ 
216.                      scanf("%d%d",&l,&r); 
217.                      tree.reverse(l,r+2); 
218.                  }else{ 
219.                      scanf("%d%d%d",&l,&r,&x); 
220.                      if(x%(r-l+1)) tree.revolve(l,r+2,x%(r-l+1)); 
221.                  } 
222.                  break; 
223.          } 
224.          getchar(); 
225.      } 
226.      return 0; 
227.  } 

先把代码贴在这里，分析的过程下一篇写！