/****************************************** 數(shù)據(jù)結(jié)構(gòu)： Splay_Tree,伸展樹;性質(zhì)： 伸展樹是二叉查找樹的一種改進(jìn); 與二叉查找樹一樣,伸展樹也具有有序性; 即伸展樹中的每一個節(jié)點(diǎn)x都滿足： 該節(jié)點(diǎn)左子樹中的每一個元素都小于x; 而其右子樹中的每一個元素都大于x; 與普通二叉查找樹不同的是，伸展樹可以自我調(diào)整;特點(diǎn)： 伸展樹并不是嚴(yán)格意義上的平衡樹; 也還是極有可能退化成線性結(jié)構(gòu),但伸展操作能使它的每一次操作近似(logn);伸展操作： 伸展操作和平衡樹的保持平衡是類似的; 只不過他不要求保持平衡,只是相應(yīng)的旋轉(zhuǎn); 旋轉(zhuǎn)有三種情況要處理： (1)Zig或Zag(節(jié)點(diǎn)x的父節(jié)點(diǎn)y是根節(jié)點(diǎn)) (2)Zig-Zig或Zag-Zag(節(jié)點(diǎn)x的父節(jié)點(diǎn)y不是根節(jié)點(diǎn)，且x與y同時是各自父節(jié)點(diǎn)的左孩子或者同時是各自父節(jié)點(diǎn)的右孩子) (3)Zig-Zag或Zag-Zig(節(jié)點(diǎn)x的父節(jié)點(diǎn)y不是根節(jié)點(diǎn)，x與y中一個是其父節(jié)點(diǎn)的左孩子而另一個是其父節(jié)點(diǎn)的右孩子) 即一字型旋轉(zhuǎn)和之字型旋轉(zhuǎn);優(yōu)勢： 能快速定位一個區(qū)間[l,r]，并且能將區(qū)間進(jìn)行刪除、旋轉(zhuǎn)操作; 將第l-1個結(jié)點(diǎn)旋轉(zhuǎn)至根(之前的Splay操作)，將第r+1個結(jié)點(diǎn)旋轉(zhuǎn)至根的右孩子; 由于伸展樹的本質(zhì)還是二叉搜索樹,則根據(jù)二叉查找樹的性質(zhì)可以知道; 在這兩個結(jié)點(diǎn)之間，也是根的右孩子的左子樹就包括節(jié)點(diǎn)[l,r]; 即很快定位了區(qū)間[l,r]，如果需要刪除，直接把子樹拿走即可;算法測試： PKU3468(A Simple Problem with Integers)題目大意: Q a b ：查詢區(qū)間[a,b]的和; C a b x : 更新區(qū)間[a,b]，區(qū)間所有值加上x; *******************************************/ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std;#define Key_value ch[ch[root][1]][0]//進(jìn)行各種操作的區(qū)間const int INF=0xffffff; const int N=100010; typedef long long LL;int ch[N][2];//左右孩子(0為左孩子，1為右孩子) int pre[N];//父結(jié)點(diǎn) int key[N];//數(shù)據(jù)域 int size[N];//樹的規(guī)模 int val[N]; int add[N]; int a[N];//結(jié)點(diǎn)元素 LL sum[N];//子樹結(jié)點(diǎn)和 int root; //根結(jié)點(diǎn) int tot;//結(jié)點(diǎn)數(shù)量 int n,q;void Push_Up(int u)//通過孩子結(jié)點(diǎn)更新父結(jié)點(diǎn) {size[u]=size[ch[u][0]]+size[ch[u][1]]+1;sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u]+add[u]; }void Push_Down(int u)//將延遲標(biāo)記更新到孩子結(jié)點(diǎn) {if(add[u]){val[u]+=add[u];add[ch[u][0]]+=add[u];add[ch[u][1]]+=add[u];sum[ch[u][0]]+=(LL)add[u]*size[ch[u][0]];sum[ch[u][1]]+=(LL)add[u]*size[ch[u][1]];add[u]=0;} }void New_Node(int &u,int f,int c)//新建一個結(jié)點(diǎn)，f為父節(jié)點(diǎn) {u=++tot;val[u]=sum[u]=c;pre[u]=f;size[u]=1;ch[u][1]=ch[u][0]=add[u]=0; }void Build_Tree(int &u,int l,int r,int f)//建樹，中間結(jié)點(diǎn)先建立，然后分別對區(qū)間兩端在左右子樹建立 {if(l>r)return;int m=(l+r)>>1;New_Node(u,f,a[m]);if(l<m)Build_Tree(ch[u][0],l,m-1,u);if(r>m)Build_Tree(ch[u][1],m+1,r,u);Push_Up(u); }void Rotate(int x,int c)//旋轉(zhuǎn)操作，c=0 表示左旋，c=1 表示右旋 {int y=pre[x];Push_Down(y);// 先將Y結(jié)點(diǎn)的標(biāo)記向下傳遞（因為Y在上面）Push_Down(x);//再把X的標(biāo)記向下傳遞ch[y][!c]=ch[x][c];//類似SBT，要把其中一個分支先給父節(jié)點(diǎn)pre[ch[x][c]]=y;pre[x]=pre[y];if(pre[y])//如果父節(jié)點(diǎn)不是根結(jié)點(diǎn)，則要和父節(jié)點(diǎn)的父節(jié)點(diǎn)連接起來{ch[pre[x]][ch[pre[y]][1]==y]=x;}pre[y]=x;ch[x][c]=y;Push_Up(y); }void Splay(int x,int f)//Splay操作,把根結(jié)點(diǎn)x轉(zhuǎn)到結(jié)點(diǎn)f的下面 {Push_Down(x);while(pre[x]!=f){int y=pre[x];if(pre[y]==f)//父結(jié)點(diǎn)的父親即為f，執(zhí)行單旋轉(zhuǎn)Rotate(x,ch[y][0]==x);else{int z=pre[y];int g=(ch[z][0]==y);if(ch[y][g]==x)Rotate(x,!g),Rotate(x,g);//之字形旋轉(zhuǎn)else Rotate(y,g),Rotate(x,g);//一字形旋轉(zhuǎn)}}Push_Up(x);// 最后再維護(hù)X結(jié)點(diǎn)if(f==0)//更新根結(jié)點(diǎn){root=x;} }void Rotate_Under(int k,int f)//把第k位的數(shù)伸展到f下方 {//找到處在中序遍歷第k個結(jié)點(diǎn)，并將其旋轉(zhuǎn)到結(jié)點(diǎn)f 的下面int p=root;//從根結(jié)點(diǎn)開始Push_Down(p);// 由于要訪問p的子結(jié)點(diǎn)，將標(biāo)記下傳while(size[ch[p][0]]!=k)//p的左子樹的大小{if(k<size[ch[p][0]])// 第k個結(jié)點(diǎn)在p左邊，向左走{p=ch[p][0];}else//否則在右邊,而且在右子樹中，這個結(jié)點(diǎn)不再是第k個{k-=(size[ch[p][0]]+1);p=ch[p][1];}Push_Down(p);}Splay(p,f);//執(zhí)行旋轉(zhuǎn) }int Insert(int k)//插入結(jié)點(diǎn) {int r=root;while(ch[r][key[r]<k])r=ch[r][key[r]<k];New_Node(ch[r][k>key[r]],r,k);//將新插入的結(jié)點(diǎn)更新至根結(jié)點(diǎn)//Push_Up(r);Splay(ch[r][k>key[r]],0);return 1; }int Get_Pre(int x)//找前驅(qū)，即左子樹的最右結(jié)點(diǎn) {int tmp=ch[x][0];if(tmp==0)return INF;while(ch[tmp][1]){tmp=ch[tmp][1];}return key[x]-key[tmp]; }int Get_Next(int x)//找后繼，即右子樹的最左結(jié)點(diǎn) {int tmp=ch[x][1];if(tmp==0)return INF;while(ch[tmp][0]){tmp=ch[tmp][0];}return key[tmp]-key[x]; }LL Query(int l,int r)//查詢[l,r]之間的和 {Rotate_Under(l-1,0);Rotate_Under(r+1,root);return sum[Key_value]; }void Update(int l,int r)//更新 {int k;scanf("%d",&k);Rotate_Under(l-1,0);Rotate_Under(r+1,root);add[Key_value]+=k;sum[Key_value]+=size[Key_value]*k; }void Init()//初始化 {for(int i=0; i<n; i++)scanf("%d",&a[i]);ch[0][0]=ch[0][1]=pre[0]=size[0]=0;add[0]=sum[0]=0;root=tot=0;New_Node(root,0,-1);New_Node(ch[root][1],root,-1); //頭尾各加入一個空位size[root]=2;Build_Tree(Key_value,0,n-1,ch[root][1]); //讓所有數(shù)據(jù)夾在兩個-1之間Push_Up(ch[root][1]);Push_Up(root); }int main() {while(~scanf("%d%d",&n,&q)){Init();while(q--){char op;scanf(" %c",&op);int x,y;scanf("%d%d",&x,&y);if(op=='Q')printf("%lld\n",Query(x,y));elseUpdate(x,y);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Spaly_Tree 模版的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。