[Dr.Lib]Note:Data Structures – 左偏树

左偏树真是个超好写的东西！支持合并，插入，删除最小值三个操作。后两个操作都可以看成第一个操作的拓展，如删除最小值是合并根的两棵子树，插入则直接将元素看作一个左偏树——所以只要写个Merge就可以了！

左偏树保证左子树深度大于等于右子树深度，同时符合堆性质。合并LT1,LT2（假设LT1中最小值比LT2小，否则交换）时，递归合并LT1的右子树和LT2替换掉LT1，然后如果LT1不符合左偏性质，则交换LT1的子树。

小小的提示：构树时，逐个插入是O(nlgn)的。这里可以有O(n)的复杂度的算法：先把所有元素构成n个单元素左偏树放进队列，然后每次取出两个合并后放入队列尾，直到只剩下一棵左偏树。

——http://seter.is-programmer.com/posts/30733.html

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstring>
#include<queue>

#define S(x) T[(x)].s
#define L(x) T[(x)].s[0]
#define Ln(x) T[T[(x)].s[0]]
#define R(x) T[(x)].s[1]
#define Rn(x) T[T[(x)].s[1]]
#define F(x) T[(x)].f
#define W(x) T[(x)].w
#define Z(x) T[(x)].size
#define D(x) T[(x)].depth

#define PB(x) push_back(x)
#define PS(x) push(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long LL;
const int MAXN=100;
const int INF=2147483647;
const int NINF=-1<<30;
const int ERR=-1;
bool getint(int &x){
    x=0;int n=1;
    char c=getchar();
    while(((c-'0')>=10)||((c-'0')<0)){n=1;if(c=='-')n=-1;c=getchar();if((int)c==-1)return false;}
    while(((c-'0')<10)&&((c-'0')>=0)){x=x*10+(c-'0');c=getchar();}x*=n;
    return true;
}
void priint(int k){
	if(!k)putchar('0');
    int t=0;char ch[30];
    while(k>0)ch[++t]=k%10,k/= 10;
    while(t)putchar(ch[t--]+'0');  
    putchar(10);  
}
struct Node{int s[2];int w;int depth;Node():w(0),depth(0){s[0]=s[1]=0;}};
Node T[MAXN];
int Merge(int a,int b){
	if(!(a&&b))return a|b;
	if(W(a)>W(b))swap(a,b);
	R(a)=Merge(R(a),b);
	if((!L(a))||D(L(a))<D(R(a)))swap(R(a),L(a));
	D(a)=L(a)?D(L(a))+1:0;
	return a;
}
int sz,root,a,b;
int main(){
	D(0)=-1;
	int x;
	while(getint(x)){
		if(!x)getint(W(++sz)),root=Merge(root,sz);
		else  priint(W(root)),root=Merge(L(root),R(root));
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<cstring>

#include<queue>

#define S(x) T[(x)].s

#define L(x) T[(x)].s[0]

#define Ln(x) T[T[(x)].s[0]]

#define R(x) T[(x)].s[1]

#define Rn(x) T[T[(x)].s[1]]

#define F(x) T[(x)].f

#define W(x) T[(x)].w

#define Z(x) T[(x)].size

#define D(x) T[(x)].depth

#define PB(x) push_back(x)

#define PS(x) push(x)

#define MP(x,y) make_pair(x,y)

using namespace std;

typedef long long LL;

const int MAXN=100;

const int INF=2147483647;

const int NINF=-1<<30;

const int ERR=-1;

bool getint(int &x){

x=0;int n=1;

char c=getchar();

while(((c-'0')>=10)||((c-'0')<0)){n=1;if(c=='-')n=-1;c=getchar();if((int)c==-1)return false;}

while(((c-'0')<10)&&((c-'0')>=0)){x=x*10+(c-'0');c=getchar();}x*=n;

return true;

}

void priint(int k){

if(!k)putchar('0');

int t=0;char ch[30];

while(k>0)ch[++t]=k%10,k/= 10;

while(t)putchar(ch[t--]+'0');

putchar(10);

}

struct Node{int s[2];int w;int depth;Node():w(0),depth(0){s[0]=s[1]=0;}};

Node T[MAXN];

int Merge(int a,int b){

if(!(a&&b))return a|b;

if(W(a)>W(b))swap(a,b);

R(a)=Merge(R(a),b);

if((!L(a))||D(L(a))<D(R(a)))swap(R(a),L(a));

D(a)=L(a)?D(L(a))+1:0;

return a;

}

int sz,root,a,b;

int main(){

D(0)=-1;

int x;

while(getint(x)){

if(!x)getint(W(++sz)),root=Merge(root,sz);

else priint(W(root)),root=Merge(L(root),R(root));

}

return 0;

}

[Dr.Lib]Note:Data Structures – Bottom-up SPLAY

Let us play！

Let u splay！

BST 平均 O(logn)

Treap 期望 O(logn)

Splay 均摊 O(logn)

AVL 严格 O(logn)

SBT 严格 O(logn)

AVL不大指望能在赛场写出来，SBT在绝大多数时候是个不错的选择，Treap…嗯……但偏偏Splay被人看成是BST中的万金油……为什么呐？

Splay一个最大的特点就是：每一个操作都要splay一下……除此之外没了……

Splay

splay操作的作用就是把某一节点旋转到根，以加快之后的访问速度。它还可以在旋转过程中维持树的基本平衡。

zig: 当目标节点是根节点的左子节点或右子节点时，进行一次zig，将目标节点调整到根节点的位置。
zig-zig:当目标节点是根节点的左（右）子节点的左（右）子节点时，进行一次zig-zig，将目标节点调整到根节点位置。
zig-zag:当目标节点是根节点的左（右）子节点的右（左）子节点时，进行一次zig-zag，将目标节点调整到根节点位置。

重复这几种操作直到目标节点为根。

一次zig、zig-zig、zig-zag又可以分解为几次单旋。

Search/Insert/Rank/Select

与BST相同，只不过记得把插入的节点Splay到根。

Join

作用是把两棵子树S1,S2连成一个Splay，其中S1中所有元素小于S2。

先找到S1中的最大节点x，Splay到S1的根，再把x的右子树链接到S2。

Delete

先找到目标节点，Splay到根，执行Join操作即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>

#define C(x) ((int)(T[T[(x)].f].s[1]==(x)))
#define S(x) T[(x)].s
#define L(x) T[(x)].s[0]
#define Ln(x) T[T[(x)].s[0]]
#define R(x) T[(x)].s[1]
#define Rn(x) T[T[(x)].s[1]]
#define F(x) T[(x)].f
#define W(x) T[(x)].w
#define Z(x) T[(x)].size
using namespace std;
typedef long long LL;
const int MAXN=300;
const int INF=2147483647;
const int NINF=-1<<30;
const int ERR=-1;

struct Node{
	int size,w,f;int s[2];//0-L,1-R;
	Node():size(0),w(0),f(0){s[0]=s[1]=0;}
};

Node T[MAXN*3];
int root,sz;
void link(int s,int f,int t){F(s)=f;S(f)[t]=s;}
void Up(int x);void Down(int x);void Join(int f,int s);
int Max(int x);int Min(int x);
void Rot(int x,int c){
	int f=F(x);
	link(x,F(f),C(f));
	link(S(x)[1^c],f,c);
	link(f,x,1^c);
	Up(f);
}
void Splay(int x,int g){
	for(Down(x);F(x)!=g;){
		int f=F(x);
		if(F(f)==g)			Rot(x,C(x));else{
			if(C(x)==C(f))	Rot(f,C(f));  
              else 			Rot(x,C(x));  
							Rot(x,C(x));  
		}
	}
	Up(x);
	if(!g)root=x;
}
void Up(int x){Z(x)=Z(L(x))+Z(R(x))+1;}
void Down(int x){/*Do YOLO*/}
void Insert(int &s,int f,int v) {
	if(s==0) {
		s=++sz;W(s)=v;Z(s)=1;F(s)=f;int x=s;Splay(x,0);
		return;
	}
	Z(s)++;
	if(W(s)>v) 	Insert(L(s),s,v);
	else		Insert(R(s),s,v);	
}
int Search(int s,int v) {
	if(s==0)return ERR;
	if(W(s)==v)return	Splay(s,0),s;
	if(W(s)>v)return 	Search(L(s),v);
	return				Search(R(s),v);
}
void Join(int l,int r){
	int lm=l;if (!l){root=r;F(r)=0; return; }
	while(R(lm))lm=R(lm);
	Splay(lm,F(l));
	R(lm)=r;
	F(r)=lm;
	F(lm)=0;
	Up(lm);
	root=lm;
}
int Delete(int s,int v){
	int x=Search(s,v);
	if(x==ERR)return ERR;
	//Splay(x,0);
	Join(L(x),R(x));
	return 0;
}
int Select(int s,int k) {
	int Lt=Z(L(s));
	if(k==Lt)return Splay(s,0),W(s);
	if(Lt>k)return	Select(L(s),k);
	return			Select(R(s),k-Lt-1);
}
int Rank(int s,int v) {
	int Lt=Z(L(s));
	if(W(s)==v)return	Splay(s,0),Lt;
	if(W(s)>v) return	Rank(L(s),v);
	return				Rank(R(s),v)+Lt+1;
}

inline bool getint(int &x){
int y,flag;
while(isspace(y=getchar()));
if(y==-1) return false;
if(y=='-') flag=-1,x=0;
else flag=1,x=y-'0';
while(isdigit(y=getchar())) x=x*10+(y-'0');
x*=flag;
return true;
}
int main(){
	int c;
	int x;
	//freopen("SBT.in6","r",stdin);
	//freopen("SBT.outsplay6","w",stdout);
	while(getint(c)) {
		switch(c) {
		case 0:
			getint(x);
			Insert(root,0,x);
			break;
		case 1:
			getint(x);
			Delete(root,x);
			break;
		case 2:
			getint(x);
			printf("%d\n",Search(root,x));
			break;
		case 3:
			getint(x);
			printf("%d\n",Select(root,x));  //x<S(root)
			break;
		case 4:
			getint(x);
			printf("%d\n",Rank(root,x));    //Search(x)>0
			break;
		default:
			printf("\n\n\n");
		}
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define C(x) ((int)(T[T[(x)].f].s[1]==(x)))

#define S(x) T[(x)].s

#define L(x) T[(x)].s[0]

#define Ln(x) T[T[(x)].s[0]]

#define R(x) T[(x)].s[1]

#define Rn(x) T[T[(x)].s[1]]

#define F(x) T[(x)].f

#define W(x) T[(x)].w

#define Z(x) T[(x)].size

using namespace std;

typedef long long LL;

const int MAXN=300;

const int INF=2147483647;

const int NINF=-1<<30;

const int ERR=-1;

struct Node{

int size,w,f;int s[2];//0-L,1-R;

Node():size(0),w(0),f(0){s[0]=s[1]=0;}

};

Node T[MAXN*3];

int root,sz;

void link(int s,int f,int t){F(s)=f;S(f)[t]=s;}

void Up(int x);void Down(int x);void Join(int f,int s);

int Max(int x);int Min(int x);

void Rot(int x,int c){

int f=F(x);

link(x,F(f),C(f));

link(S(x)[1^c],f,c);

link(f,x,1^c);

Up(f);

}

void Splay(int x,int g){

for(Down(x);F(x)!=g;){

int f=F(x);

if(F(f)==g) Rot(x,C(x));else{

if(C(x)==C(f)) Rot(f,C(f));

else Rot(x,C(x));

Rot(x,C(x));

}

Up(x);

if(!g)root=x;

}

void Up(int x){Z(x)=Z(L(x))+Z(R(x))+1;}

void Down(int x){/*Do YOLO*/}

void Insert(int &s,int f,int v) {

if(s==0) {

s=++sz;W(s)=v;Z(s)=1;F(s)=f;int x=s;Splay(x,0);

return;

}

Z(s)++;

if(W(s)>v) Insert(L(s),s,v);

else Insert(R(s),s,v);

}

int Search(int s,int v) {

if(s==0)return ERR;

if(W(s)==v)return Splay(s,0),s;

if(W(s)>v)return Search(L(s),v);

return Search(R(s),v);

}

void Join(int l,int r){

int lm=l;if (!l){root=r;F(r)=0; return; }

while(R(lm))lm=R(lm);

Splay(lm,F(l));

R(lm)=r;

F(r)=lm;

F(lm)=0;

Up(lm);

root=lm;

}

int Delete(int s,int v){

int x=Search(s,v);

if(x==ERR)return ERR;

//Splay(x,0);

Join(L(x),R(x));

return 0;

}

int Select(int s,int k) {

int Lt=Z(L(s));

if(k==Lt)return Splay(s,0),W(s);

if(Lt>k)return Select(L(s),k);

return Select(R(s),k-Lt-1);

}

int Rank(int s,int v) {

int Lt=Z(L(s));

if(W(s)==v)return Splay(s,0),Lt;

if(W(s)>v) return Rank(L(s),v);

return Rank(R(s),v)+Lt+1;

}

inline bool getint(int &x){

int y,flag;

while(isspace(y=getchar()));

if(y==-1) return false;

if(y=='-') flag=-1,x=0;

else flag=1,x=y-'0';

while(isdigit(y=getchar())) x=x*10+(y-'0');

x*=flag;

return true;

}

int main(){

int c;

int x;

//freopen("SBT.in6","r",stdin);

//freopen("SBT.outsplay6","w",stdout);

while(getint(c)) {

switch(c) {

case 0:

getint(x);

Insert(root,0,x);

break;

case 1:

getint(x);

Delete(root,x);

break;

case 2:

getint(x);

printf("%d\n",Search(root,x));

break;

case 3:

getint(x);

printf("%d\n",Select(root,x)); //x<S(root)

break;

case 4:

getint(x);

printf("%d\n",Rank(root,x)); //Search(x)>0

break;

default:

printf("\n\n\n");

}

return 0;

}

[Dr.Lib]Note:Data Structures – Size Balanced Tree – II

。。也没什么好说的了，《Size Balanced Tree》（CQF WC 2006）说的很清楚了……

今晚（昨晚？手敲的代码……不知道如何……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define L(x) T[(x)].ls
#define Ln(x) T[T[(x)].ls]
#define R(x) T[(x)].rs
#define Rn(x) T[T[(x)].ls]
#define W(x) T[(x)].w
#define S(x) T[(x)].size
using namespace std;

const int MAXN=100000;
const int INF=2147483647;
int root=0;

struct Node{
	int ls,rs,size,w;
	Node():ls(0),rs(0),size(0),w(0){}
};
Node T[MAXN];
int sz,n;

void RR(int &s){
	int x = s;
	int k=L(s);
	L(s)=R(k);
	R(k)=s;
	S(k)=S(s);
	S(s)=S(L(s))+S(R(s))+1;
	s = k;
}
void LR(int &s){
	int x = s;
	int k=R(s);
	R(s)=L(k);
	L(k)=s;
	S(k)=S(s);
	S(s)=S(L(s))+S(R(s))+1;
	s = k;
}
void Maintain(int &s,bool op){
	if (s == 0)return;
	if(!op){
		if( S(R(s)) < S(L(L(s))) )RR(s);
		else if( S(R(s)) < S(R(L(s))) ){
			LR(L(s));RR(s);
		}
		else  return;
	}else{
		if( S(L(s)) < S(R(R(s))) )LR(s);
		else if( S(L(s)) < S(L(R(s))) ){
			RR(R(s));LR(s);
		}
		else  return;
	}
	Maintain(L(s),false);
	Maintain(R(s),true);
	Maintain(s,false);
	Maintain(s,true);
}
void Insert(int &s,int val){
	if(s==0){
		s=++sz;S(s)++;W(s)=val;return;
	}
	S(s)++;
	if(W(s)>val)Insert(L(s),val);
	else Insert(R(s),val);
	Maintain(s,(val>=W(s)));
}
int Delete(int &s,int v){
	S(s)--;
	if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){
		int ans=W(s);
		if(!(L(s)*R(s))){
			s=L(s)+R(s);
		}else{
			W(s)=Delete(L(s),W(s)+1);
		}
		return ans;
	}else{
		if(W(s)>v) return Delete(L(s),v); 
		else       return Delete(R(s),v);
	}
}
int Search(int &s,int v){
	if(!s)return INF;
	if(v==W(s))return s;
	else if(W(s)>v) return Search(L(s),v);
	else            return Search(R(s),v);
}
int Select(int &s,int k){
	if(k>S(root)) return INF;
	int Lt=S(L(s));
	if(k==Lt) return W(s);
	else if(Lt>k) return Select(L(s),k);
	else          return Select(R(s),k-Lt-1);
}
int Rank(int &s,int x){
	if(!s)return INF;
	int Lt=S(L(s));
	if(x==W(s))return Lt;
	else if(W(s)>x)return Rank(L(s),x);
	else           return Rank(R(s),x)+Lt+1;
}
int main(){
	int c;
	int x;
	while(cin>>c>>x){
		switch(c){
			case 0:Insert(root,x);break;
			case 1:Delete(root,x);break;
			case 2:cout<<Search(root,x)<<endl;break;
			case 3:cout<<Select(root,x)<<endl;break;
			case 4:cout<<Rank(root,x)<<endl;break;
			default:cout<<endl;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define L(x) T[(x)].ls

#define Ln(x) T[T[(x)].ls]

#define R(x) T[(x)].rs

#define Rn(x) T[T[(x)].ls]

#define W(x) T[(x)].w

#define S(x) T[(x)].size

using namespace std;

const int MAXN=100000;

const int INF=2147483647;

int root=0;

struct Node{

int ls,rs,size,w;

Node():ls(0),rs(0),size(0),w(0){}

};

Node T[MAXN];

int sz,n;

void RR(int &s){

int x = s;

int k=L(s);

L(s)=R(k);

R(k)=s;

S(k)=S(s);

S(s)=S(L(s))+S(R(s))+1;

s = k;

}

void LR(int &s){

int x = s;

int k=R(s);

R(s)=L(k);

L(k)=s;

S(k)=S(s);

S(s)=S(L(s))+S(R(s))+1;

s = k;

}

void Maintain(int &s,bool op){

if (s == 0)return;

if(!op){

if( S(R(s)) < S(L(L(s))) )RR(s);

else if( S(R(s)) < S(R(L(s))) ){

LR(L(s));RR(s);

}

else return;

}else{

if( S(L(s)) < S(R(R(s))) )LR(s);

else if( S(L(s)) < S(L(R(s))) ){

RR(R(s));LR(s);

}

else return;

}

Maintain(L(s),false);

Maintain(R(s),true);

Maintain(s,false);

Maintain(s,true);

}

void Insert(int &s,int val){

if(s==0){

s=++sz;S(s)++;W(s)=val;return;

}

S(s)++;

if(W(s)>val)Insert(L(s),val);

else Insert(R(s),val);

Maintain(s,(val>=W(s)));

}

int Delete(int &s,int v){

S(s)--;

if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){

int ans=W(s);

if(!(L(s)*R(s))){

s=L(s)+R(s);

}else{

W(s)=Delete(L(s),W(s)+1);

}

return ans;

}else{

if(W(s)>v) return Delete(L(s),v);

else return Delete(R(s),v);

}

int Search(int &s,int v){

if(!s)return INF;

if(v==W(s))return s;

else if(W(s)>v) return Search(L(s),v);

else return Search(R(s),v);

}

int Select(int &s,int k){

if(k>S(root)) return INF;

int Lt=S(L(s));

if(k==Lt) return W(s);

else if(Lt>k) return Select(L(s),k);

else return Select(R(s),k-Lt-1);

}

int Rank(int &s,int x){

if(!s)return INF;

int Lt=S(L(s));

if(x==W(s))return Lt;

else if(W(s)>x)return Rank(L(s),x);

else return Rank(R(s),x)+Lt+1;

}

int main(){

int c;

int x;

while(cin>>c>>x){

switch(c){

case 0:Insert(root,x);break;

case 1:Delete(root,x);break;

case 2:cout<<Search(root,x)<<endl;break;

case 3:cout<<Select(root,x)<<endl;break;

case 4:cout<<Rank(root,x)<<endl;break;

default:cout<<endl;

}

return 0;

}

[Dr.Lib]Note:Data Structures – Size Balanced Tree – I

。。按惯例笔记贴都是摘抄、转载的……TAT看了半天貌似还是不会写的样子……滚回去复习主席树了

Via NOCOW http://www.nocow.cn/index.php/Size_Balanced_Tree

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB，编写起来也并不BT。恰恰相反，SBT易于实现，且据陈启峰论文中所言，“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank。

性质

Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树，它也因此得名。它总是满足：
对于SBT的每一个结点 t：

性质(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]
性质(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。

如图（圈代表结点，三角代表SBT，下同）：

s[R] ≥ s[A]，s[B]
s[L] ≥ s[C]，s[D]

旋转

SBT的旋转（Rotations）与其他许多高级BST相同。它是下面提到的Maintain操作的基础。

k ← right[t]
right[t] ← left[k]
left[k] ← t
s[k] ← s[t]
s[t] ← s[left[t]] + s[right[t]] + 1
t ← k

k ← right[t]

right[t] ← left[k]

left[k] ← t

s[k] ← s[t]

s[t] ← s[left[t]] + s[right[t]] + 1

t ← k

k ← left[t]
left[t] ← right[k]
right[k] ← t
s[k] ← s[t]
s[t] ← s[left[t]] + s[right[t]] + 1
t ← k

k ← left[t]

left[t] ← right[k]

right[k] ← t

s[k] ← s[t]

s[t] ← s[left[t]] + s[right[t]] + 1

t ← k

保持性质(Maintain)

当我们插入或删除一个结点后，SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时，我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程；Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。

第一种情况：s[left[left[t]]>s[right[t]]如图3，执行完Insert(left[t],v)后发生S[A]>S[R]，我们可以执行以下的指令来修复SBT：
1. 首先执行Right-Ratote(t)，这个操作让图3变成图4；
2. 在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
第二种情况：s[right[left[t]]>s[right[t]]在执行完Insert(left[t],v)后发生s[B]>s[R]，如图5，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复：
1. 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
2. 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图7。
3. 在第1步和第2步过后，整棵树就变得非常不可预料了。万幸的是，在图7中，子树A、E、F和R仍就是SBT，所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
4. 在第3步之后，子树都已经是SBT了，但是在结点B上还可能不满足性质a或性质b，因此我们需要再一次调用Maintain(B)。
第三种情况：s[right[right[t]]>s[left[t]]
与情况1对称。
第四种情况：s[left[right[t]]>s[left[t]]
与情况2对称。

通过前面的分析，很容易写出一个普通的Maintain。

 If s[left[left[t]]>s[right[t]] then    //case1
      Right-Rotate(t)
      Maintain(right[t])
      Maintain(t)
      Exit
 If s[left[right[t]]>s[right[t]] then   //case2
      Left-Rotate(left[t])
      Right-Rotate(t)
      Maintain(left[t])
      Maintain(right[t])
      Maintain(t)
      Exit
 If s[right[right[t]]>s[left[t]] then   //case1'
      Left-Rotate(t)
      Maintain(left[t])
      Maintain(t)
      Exit
 If s[right[left[t]]>s[left[t]] then    //case2'
      Right-Rotate(right[t])
      Left-Rotate(t)
      Maintain(left[t])
      Maintain(right[t])
      Maintain(t)

If s[left[left[t]]>s[right[t]] then //case1

Right-Rotate(t)

Maintain(right[t])

Maintain(t)

Exit

If s[left[right[t]]>s[right[t]] then //case2

Left-Rotate(left[t])

Right-Rotate(t)

Maintain(left[t])

Maintain(right[t])

Maintain(t)

Exit

If s[right[right[t]]>s[left[t]] then //case1'

Left-Rotate(t)

Maintain(left[t])

Maintain(t)

Exit

If s[right[left[t]]>s[left[t]] then //case2'

Right-Rotate(right[t])

Left-Rotate(t)

Maintain(left[t])

Maintain(right[t])

Maintain(t)

前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量：flag，来避免毫无意义的判断。如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。

 If flag=false then
       If s[left[left[t]]>s[right[t]] then      //case1
           Right-Rotate(t)
       Else
           If s[left[right[t]]>s[right[t]] then   //case2
                Left-Rotate(left[t])
                Right-Rotate(t)
      Else                                   //needn’t repair
           Exit
 Else
       If s[right[right[t]]>s[left[t]] then      //case1'
           Left-Rotate(t)
      Else
           If s[right[left[t]]>s[left[t]] then     //case2'
                Right-Rotate(right[t])
                Left-Rotate(t)
      Else                                    //needn’t repair
           Exit
 Maintain(left[t],false)                     //repair the left subtree
 Maintain(right[t],true)                     //repair the right subtree
 Maintain(t,false)                           //repair the whole tree
 Maintain(t,true)                            //repair the whole tree

If flag=false then

If s[left[left[t]]>s[right[t]] then //case1

Right-Rotate(t)

Else

If s[left[right[t]]>s[right[t]] then //case2

Left-Rotate(left[t])

Right-Rotate(t)

Else //needn’t repair

Exit

Else

If s[right[right[t]]>s[left[t]] then //case1'

Left-Rotate(t)

Else

If s[right[left[t]]>s[left[t]] then //case2'

Right-Rotate(right[t])

Left-Rotate(t)

Else //needn’t repair

Exit

Maintain(left[t],false) //repair the left subtree

Maintain(right[t],true) //repair the right subtree

Maintain(t,false) //repair the whole tree

Maintain(t,true) //repair the whole tree

为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？

……且听下回分解

[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

偶然间翻PDF时看到了FHQ神犇的WC论文……看了一遍没记住什么……除了函数式编程其他也……就那样吧……顺手把CLJ的论文也看了一遍……//可持久化做法很多，函数式是种比较科学的实现……暴力复制、wzk树什么的就不说了……

然后函数式编程早就接触过但从来没有研究过TAT显然函数式线段树最成功的应用(之一?）就是主席树了……

函数式编程

修改元素是数据结构的一个基本操作，平常的实践中我们比较常见的就是直接改储存的值，而函数式编程中，我们从不去修改值，而是再定义一个。

对应在线段树操作中，我们每次修改值，都不会去修改任何节点，而是返回一棵新的树。

函数式Treap假想图函数式线段树

图片来自范浩强_wc2012谈谈各种数据结构

因为保证所有节点都不会被修改，所以我们可以重用未受影响的节点。显然，函数式线段树中，插入操作的时间、空间复杂度都是O(log n)，其他操作与正常线段树无异。

主席树

主席树是一种利用函数式线段树维护数列的数据结构，一般用来解决区间第K大数问题。设数列长度为NN，数据范围为n，已离散化。

不支持修改的主席树（前缀和主席树）

……不支持修改的主席树在我的笔记中记为前缀和主席树…自己取的名字。。。

前缀和主席树由N棵线段树组成，第i棵Ti是对于[1,i]建一棵以序列里的值为下标，储存区间里出现该值的次数的线段树，也可以看作是Ti-1插入a[i]后的线段树。

注意到所有的树是同构(?)的，Ts-1和Tt可以直接相减得到T[s,t]，在树上进行二分就可以得到区间K大值。

当然，所有的线段树都指函数式线段树。

代码：Via http://www.cnblogs.com/Rlemon/archive/2013/05/23/3094635.html 我自己码的实现惨不忍睹…这是和我的风格最接近的一个…以下是按我的笔记格式码的…

#define w(i) T[(i)].w
#define ls(i) T[(i)].ls
#define rs(i) T[(i)].rs
using namespace std;
const int MAXNN;
struct node{
    int ls,rs,w;
    node(){ls=rs=w=0;}
}T[MAXNN*20];
int a[MAXNN],root[MAXNN],sz,m;

void ins(int &i,int l,int r,int x){
    T[++sz]=T[i]; i=sz;
    w(i)++;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) ins(ls(i),l,m,x);
    else ins(rs(i),m+1,r,x);
}
int query(int i,int j,int l,int r,int k){
    if (l==r) return l;
    int t=w(ls(j))-w(ls(i));
    int m=(l+r)>>1;
    if (t>=k) return query(ls(i),ls(j),l,m,k);
    else return query(rs(i),rs(j),m+1,r,k-t);
}
int main(){
        //DO YOLO
        root[0]=0;
        sz=0;
        for (int i=1;i<=N;i++){
            root[i]=root[i-1];
            ins(root[i],1,n,a[i]);
        }
        //支持操作：
            //QUERY(s,t,k):query(root[s-1],root[T],1,n,k);

    return 0;
}

#define w(i) T[(i)].w

#define ls(i) T[(i)].ls

#define rs(i) T[(i)].rs

using namespace std;

const int MAXNN;

struct node{

int ls,rs,w;

node(){ls=rs=w=0;}

}T[MAXNN*20];

int a[MAXNN],root[MAXNN],sz,m;

void ins(int &i,int l,int r,int x){

T[++sz]=T[i]; i=sz;

w(i)++;

if (l==r) return;

int m=(l+r)>>1;

if (x<=m) ins(ls(i),l,m,x);

else ins(rs(i),m+1,r,x);

}

int query(int i,int j,int l,int r,int k){

if (l==r) return l;

int t=w(ls(j))-w(ls(i));

int m=(l+r)>>1;

if (t>=k) return query(ls(i),ls(j),l,m,k);

else return query(rs(i),rs(j),m+1,r,k-t);

}

int main(){

//DO YOLO

root[0]=0;

sz=0;

for (int i=1;i<=N;i++){

root[i]=root[i-1];

ins(root[i],1,n,a[i]);

}

//支持操作：

//QUERY(s,t,k):query(root[s-1],root[T],1,n,k);

return 0;

}

支持修改的主席树（树状主席树）

还记得当年学数据结构时如何维护带修改区间[s,t]的区间和吗？

树状数组，简单高效。既然我们维护的是一个线段树的前缀和，何不用树状数组维护呢？

脑补一棵树状数组，每个节点是一棵线段树。修改时，我们仅需修改log n棵线段树即可。

//貌似只有我叫它树状主席树……正解是树状数组套主席树。

代码

#define ls(i) T[i].ls
#define rs(i) T[i].rs
#define w(i) T[i].w

using namespace std;
const int MAXNN;
struct node{
    int ls,rs,w;
    node(){ls=rs=w=0;}
}T[MAXNN*20];
vector<int> Ql,Qr;
int n,m,sz,NN;

int a[MAXNN],root[MAXNN],rooto[MAXNN];
inline int lowbit(int x){
    return x&-x;
}
void build(int &i,int l,int r,int x){
    T[++sz]=T[i]; i=sz;
    w(i)++;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) build(ls(i),l,m,x);
    else build(rs(i),m+1,r,x);
}
void ins(int &i,int l,int r,int x,int v){
    if (i==0){ T[++sz]=T[i]; i=sz; }
    w(i)+=v;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) ins(ls(i),l,m,x,v);
    else ins(rs(i),m+1,r,x,v);
}
void BITins(int pos,int x,int v){
    for (int i=pos;i<=NN;i+=lowbit(i)){
        ins(root[i],1,n,x,v);
    }
}
int  STquery(vector<int> Q1,vector<int> Q2,int l,int r,int k){
    if (l==r) return l;
    int c=0;
    int m=(l+r)>>1;
	//查询[l,m]
    for (int i=0;i<Q1.size();i++) c-=w(ls(Q1[i]));
    for (int i=0;i<Q2.size();i++) c+=w(ls(Q2[i]));
	//线段树上二分
    for (int i=0;i<Q1.size();i++) Q1[i]=(c>=k?ls(Q1[i]):rs(Q1[i]));
    for (int i=0;i<Q2.size();i++) Q2[i]=(c>=k?ls(Q2[i]):rs(Q2[i]));

    if (c>=k) return STquery(Q1,Q2,l,m,k);
    else return STquery(Q1,Q2,m+1,r,k-c);
}
int query(int l,int r,int k){
    Ql.clear();Qr.clear();
	//原始数组
    Ql.push_back(rooto[l-1]);
    Qr.push_back(rooto[r]);
	//操作数，用树状数组维护
    for (int i=l-1;i>0;i-=lowbit(i)) Ql.push_back(root[i]);
    for (int i=r;i>0;i-=lowbit(i)) Qr.push_back(root[i]);
    return STquery(Ql,Qr,1,n,k);
}
int main(){
    //DO YOLO
    sz=0;
    memset(rooto,0,sizeof(rooto));
    memset(root,0,sizeof(root));
    for (int i=1;i<=n;i++){
        rooto[i]=rooto[i-1];
        build(rooto[i],1,n,a[i]);
    }
    //支持操作：
	//UPDATE(x,v):[
	//    BITins(x,a[x],-1);
	//    BITins(x,v,1);
	//    a[x]=v;
	//]
	//QUERY(s,t,k):[
	//    query(s,t,k);
	//]
}

#define ls(i) T[i].ls

#define rs(i) T[i].rs

#define w(i) T[i].w

using namespace std;

const int MAXNN;

struct node{

int ls,rs,w;

node(){ls=rs=w=0;}

}T[MAXNN*20];

vector<int> Ql,Qr;

int n,m,sz,NN;

int a[MAXNN],root[MAXNN],rooto[MAXNN];

inline int lowbit(int x){

return x&-x;

}

void build(int &i,int l,int r,int x){

T[++sz]=T[i]; i=sz;

w(i)++;

if (l==r) return;

int m=(l+r)>>1;

if (x<=m) build(ls(i),l,m,x);

else build(rs(i),m+1,r,x);

}

void ins(int &i,int l,int r,int x,int v){

if (i==0){ T[++sz]=T[i]; i=sz; }

w(i)+=v;

if (l==r) return;

int m=(l+r)>>1;

if (x<=m) ins(ls(i),l,m,x,v);

else ins(rs(i),m+1,r,x,v);

}

void BITins(int pos,int x,int v){

for (int i=pos;i<=NN;i+=lowbit(i)){

ins(root[i],1,n,x,v);

}

int STquery(vector<int> Q1,vector<int> Q2,int l,int r,int k){

if (l==r) return l;

int c=0;

int m=(l+r)>>1;

//查询[l,m]

for (int i=0;i<Q1.size();i++) c-=w(ls(Q1[i]));

for (int i=0;i<Q2.size();i++) c+=w(ls(Q2[i]));

//线段树上二分

for (int i=0;i<Q1.size();i++) Q1[i]=(c>=k?ls(Q1[i]):rs(Q1[i]));

for (int i=0;i<Q2.size();i++) Q2[i]=(c>=k?ls(Q2[i]):rs(Q2[i]));

if (c>=k) return STquery(Q1,Q2,l,m,k);

else return STquery(Q1,Q2,m+1,r,k-c);

}

int query(int l,int r,int k){

Ql.clear();Qr.clear();

//原始数组

Ql.push_back(rooto[l-1]);

Qr.push_back(rooto[r]);

//操作数，用树状数组维护

for (int i=l-1;i>0;i-=lowbit(i)) Ql.push_back(root[i]);

for (int i=r;i>0;i-=lowbit(i)) Qr.push_back(root[i]);

return STquery(Ql,Qr,1,n,k);

}

int main(){

//DO YOLO

sz=0;

memset(rooto,0,sizeof(rooto));

memset(root,0,sizeof(root));

for (int i=1;i<=n;i++){

rooto[i]=rooto[i-1];

build(rooto[i],1,n,a[i]);

}

//支持操作：

//UPDATE(x,v):[

// BITins(x,a[x],-1);

// BITins(x,v,1);

// a[x]=v;

//]

//QUERY(s,t,k):[

// query(s,t,k);

//]

}

临时建立节点的主席树

//待补完
参见clj的wc论文

Tag Archives: data structures

[Dr.Lib]Note:Data Structures – 左偏树

[Dr.Lib]Note:Data Structures – Bottom-up SPLAY

Splay

Search/Insert/Rank/Select

Join

Delete

代码

[Dr.Lib]Note:Data Structures – Size Balanced Tree – II

[Dr.Lib]Note:Data Structures – Size Balanced Tree – I

性质

旋转

保持性质(Maintain)

[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

函数式编程

主席树

不支持修改的主席树（前缀和主席树）

支持修改的主席树（树状主席树）

临时建立节点的主席树

朋友们

TAG CLOUD