Don't let your dreams be dreams.

WELCOME——一只蒟蒻的幻想

| 笔记, 数据结构, 平衡树

闲来无事学数据结构——非旋转Treap

星期六的模拟赛里的在线段树上打可持久化Treap的标记感觉好神的样子，就想去学一学。然后Memphis的blog一直崩一直崩woc，要么刷不出图片要么刷不出代码，is-programmer服务器真是妈的智障。


好吧让我先来口胡一下Treap是什么(然而我并不会Treap233,从来都是写Spaly的233),顾名思义Treap就是tree+heap.所以Treap就是拥有堆性质的二叉树.对于Treap里的每一个节点拥有两个值,fix和key.对于fix满足堆性质,在任意一颗子树中,根节点的fix为最小值.对于key,满足中序遍历有序.
对于插入删除节点的操作可以用旋转来维护Treap的性质，至于怎么旋转嘛。。我不知道，应该和Splay差不多的吧。

好上面的都不是重点，并没有什么用处(其实只是我编不下去了)
旋转Treap相较与Splay优点是常数小，但是，好像并不能方便地实现区间的操作。(所以还是Splay大法好啊233)

所以需要一种可以支持区间操作的Treap，于是非旋转Treap就出现了。
非旋转Treap可以做什么：

  • Build建树
  • Split分裂
  • Merge合并

好像没什么用啊。
但是通过分裂合并就可以提取出一段区间，然后就可以进行区间操作，下传标记等一系列操作。

具体操作的分析

Build

Treap可以实现O(N)建树，具体方法就是用栈维护树右边的一条链，然后每次在树右下角加一个点，维护Treap的性质。
如果栈顶的元素fix值大于插入点的fix，就将栈顶元素弹出。
直到站栈中元素fix满足递增，将弹出的点接在新插入点的左儿子。
复杂度分析：因为每一个点只被弹出一次，所以复杂度为O(N)的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
node *Build(){
	static node *stk[N],*x,*last = null;
	int top = 0;
	for (int i=1;i<=n;i++){
		tot++;x = Nd+tot;x->val = i;last = null;
		while (top && stk[top]->fix>x->fix) {
			stk[top]->Update();
			last = stk[top];
			stk[top--] = null;
		}
		if (top) stk[top]->R = x;
		x->L = last;
		stk[++top] = x;
//		print(stk[1]);puts("");
	}
	while (top) stk[top--]->Update();
	return stk[1];
}

Split

将一颗Treap按照第K位分裂成两半。
就像找第K位一样递归下去，返回的时候合并一下就好了。
复杂度分析：因为Treap期望的树高为Log的，所以Split一次的复杂度为O(LogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Droot Split(node *x,int k) {
	if (x==null) return Droot(null,null);
	Droot y;
	x->Down();
	if (x->L->S>=k) {
		y = Split(x->L,k);
		x->L = y.second;
		x->Update();
		y.second = x;
	}
	else {
		y = Split(x->R,k-x->L->S-1);
		x->R = y.first;
		x->Update();
		y.first = x;
	}
	return y;
}
为了可以看清楚没有缩行，其实代码是很短的。

Merge

将两颗相对有序的Treap合并，注意是相对有序，即第一棵Treap的右下角的值要小于第二棵Treap的左下角值。如果不是相对有序的Treap只能通过启发式合并。
合并的时候因为要考虑fix值满足堆性质，可以像可并堆一样地合并，比较根节点的fix，然后递归合并儿子。不过因为要满足Treap的性质，不能交换左右儿子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
node *Merge(node *A,node *B){
	if (A==null && B==null) return null;
	if (A==null) return B;
	if (B==null) return A;
	if (A->fix<B->fix){
		A->Down();
		A->R = Merge(A->R,B);
		A->Update();
		return A;
	}
	else {
		B->Down();
		B->L = Merge(A,B->L);
		B->Update();
		return B;
	}
}

有了这些操作就可以很方便的实现大部分区间操作和删除插入操作。

我们发现这些操作都是从上向下的，所以不需要记父亲。于是，Treap就可以实现可持久化了。
至于怎么实现。我并不知道。学习ing

最后贴一道BZOJ3223的代码，区间翻转.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 100010;
using namespace std;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int n,m,l,r,tot;
struct node *null,*rt;
struct node{
	node *L,*R;int S,fix,val,rev;
	void Update(){if (this==null) return;S = L->S+R->S+1;}
	void Setrev(){if (this==null) return;rev^=1;swap(L,R);}
	void Down(){if (this==null) return;if (rev){rev = 0;L->Setrev();R->Setrev();}}
} Nd[N];
typedef pair<node*,node*> Droot;
void print(node *x){if (x==null) return;x->Down();print(x->L);printf("%d ",x->val);print(x->R);}
node *Build(){
	static node *stk[N],*x,*last = null;
	int top = 0;
	for (int i=1;i<=n;i++){
		tot++;x = Nd+tot;x->val = i;last = null;
		while (top && stk[top]->fix>x->fix) {stk[top]->Update();last = stk[top];stk[top--] = null;}
		if (top) stk[top]->R = x;x->L = last;stk[++top] = x;
	}
	while (top) stk[top--]->Update();
	return stk[1];
}
node *Merge(node *A,node *B){
	if (A==null && B==null) return null;
	if (A==null) return B;if (B==null) return A;
	if (A->fix<B->fix){A->Down();A->R = Merge(A->R,B);A->Update();return A;}
	else {B->Down();B->L = Merge(A,B->L);B->Update();return B;}
}
Droot Split(node *x,int k) {
	if (x==null) return Droot(null,null);
	Droot y;x->Down();
	if (x->L->S>=k) {y = Split(x->L,k);x->L = y.second;x->Update();y.second = x;}
	else {y = Split(x->R,k-x->L->S-1);x->R = y.first;x->Update();y.first = x;}
	return y;
}
void Reverse(int l,int r){
	if (l==1 && r==n) {rt->Setrev();return;}
	if (l==1) {Droot x = Split(rt,r);x.first->Setrev();rt = Merge(x.first,x.second);return;}
	if (r==n) {Droot x = Split(rt,l-1);x.second->Setrev();rt = Merge(x.first,x.second);return;}
	Droot x = Split(rt,l-1);
	Droot y = Split(x.second,r-(l-1));
	y.first->Setrev();
	rt = Merge(Merge(x.first,y.first),y.second);
}
int main(){
	n = read();m = read();null = Nd;
	for (int i=0;i<=n;i++) Nd[i] = (node){null,null,1,rand(),0};
	null->S = 0;rt = Build();
	for (int i=1;i<=m;i++) {l = read();r = read();Reverse(l,r);}
	print(rt);
}

代码长度和Splay差不了多少，至于常数嘛。。这道题上好像也看不出来什么。差了200ms也算还能够接受。

有错误请指出$$\mathcal {FIN}$$