lemonoil

OI__nothing is impossible

后缀平衡树

• 标签: 后缀平衡树 后缀 平衡树 treap

本是打算研究后缀结构，但是发现不管是倍增还是DC3都异常容易错，知道最近才学习到了倍增算法的简易写法，但是仍然不爽，于是乎进入了后缀平衡树这样一个大坑。 这里写图片描述

风雨，残花，遇见你

首先遇到的一个问题就是treap常数太大，虽然网上的裸题可以过，但是却异常的缓慢。。。。 以bzoj3682为例 用treap解决为2400ms 

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
----------
template<class T>inline void read(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;
}
#define N 500010
#define LL long long
int n,m,len,type,lastans,x,y;
int ch[N][2],rd[N],cl[N],cnt,root;
LL rk[N];
inline int randlmy(){
	static int seed=173;
    return seed=int(seed*48271LL%2147483647);
}
int cmp(int x,int y){
	return cl[x]<cl[y]||(cl[x]==cl[y]&&rk[x-1]<rk[y-1]);
}
void rebuild(int &rt,LL l,LL r){
	if(!rt)return;
	rk[rt]=l+r;
	LL mid=(l+r)>>1;
	rebuild(ch[rt][0],l,mid);
	rebuild(ch[rt][1],mid,r);
	
}
void rotate(int &p,int d,LL l,LL r){
	int q=ch[p][d^1];
	ch[p][d^1]=ch[q][d];
	ch[q][d]=p;
	p=q;
	rebuild(p,l,r);
}
void insert(int &rt,LL l,LL r){
	LL mid=(r+l)>>1;
	if(!rt){rt=cnt;rk[rt]=l+r;return;}
	if(cmp(cnt,rt)){insert(ch[rt][0],l,mid);if(rd[ch[rt][0]]>rd[rt])rotate(rt,1,l,r);}
    else{insert(ch[rt][1],mid,r);if(rd[ch[rt][1]]>rd[rt])rotate(rt,0,l,r);}
}
void insert(int v){
	cl[++cnt]=v;
	rd[cnt]=randlmy()*randlmy();
	insert(root,1,1LL<<61);
}
#define R(rt) rt<<1|1
#define L(rt) rt<<1
int minn[N<<2],p[N];
void build(int rt,int l,int r){
	if(l==r)read(p[l]),minn[rt]=l;
	else{
		int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
		build(lc,l,mid);
		build(rc,mid+1,r);
		minn[rt]=rk[p[minn[lc]]]<=rk[p[minn[rc]]]?minn[lc]:minn[rc];
	}
}
void updata(int rt,int l,int r,int id){
	if(l==r)return;
	int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
	if(id<=mid)updata(lc,l,mid,id);
	else updata(rc,mid+1,r,id);
	minn[rt]=rk[p[minn[lc]]]<=rk[p[minn[rc]]]?minn[lc]:minn[rc];
}
int query(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return minn[rt];
	int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
	if(qr<=mid)return query(lc,l,mid,ql,qr);
	if(ql>mid)return query(rc,mid+1,r,ql,qr);
	int vl=query(lc,l,mid,ql,qr),vr=query(rc,mid+1,r,ql,qr);
	return rk[p[vl]]<=rk[p[vr]]?vl:vr;
}
char s[N],cmd[5];
int main(){
	read(n),read(m),read(len),read(type);
	scanf("%s",s);
	for(register int i=1;i<=len;i++)
		insert(s[len-i]-'a');
	build(1,1,n);
	while(m--){
		scanf("%s",cmd);
		if(!type)lastans=0;
		if(cmd[0]=='I')
			read(x),insert(x^lastans),++len;
		else if(cmd[0]=='C')
			read(x),read(p[x]),updata(1,1,n,x);
		else
			read(x),read(y),
			printf("%d\n",lastans=query(1,1,n,x,y));
	}
	return 0;
}

而同等条件下，我生硬地植入SBT，所得结果出人意料 用时1600ms

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;
}
#define N 500010
#define LL long long
int n,m,len,type,lastans,x,y;
int ch[N][2],sz[N],cl[N],cnt,root;
LL rk[N];
int cmp(int x,int y){
	return cl[x]<cl[y]||(cl[x]==cl[y]&&rk[x-1]<rk[y-1]);
}
void rebuild(int &rt,LL l,LL r){
	if(!rt)return;
	rk[rt]=l+r;
	LL mid=(l+r)>>1;
	rebuild(ch[rt][0],l,mid);
	rebuild(ch[rt][1],mid,r);
}
void left_rot(int &x,LL l,LL r) {
    int y=ch[x][1];
    ch[x][1]=ch[y][0];
    ch[y][0]=x;
    sz[y]=sz[x]; 
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    x=y;
    rebuild(x,l,r);
}
void right_rot(int &x,LL l,LL r) {
    int y=ch[x][0];
    ch[x][0]=ch[y][1];
    ch[y][1]=x;
    sz[y]=sz[x];
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    x=y;
    rebuild(x,l,r);
}
void maintain(int &x,bool f,LL l,LL r) {
    if(f == 0) {
        if(sz[ch[ch[x][0]][0]] > sz[ch[x][1]]) {
            right_rot(x,l,r);
        }else if(sz[ch[ch[x][0]][1]] > sz[ch[x][1]]) {
            left_rot(ch[x][0],l,r);
            right_rot(x,l,r);
        }else return ;
    }else{
        if(sz[ch[ch[x][1]][1]] > sz[ch[x][0]]) { 
            left_rot(x,l,r);
        }else if(sz[ch[ch[x][1]][0]] > sz[ch[x][0]]) { 
            right_rot(ch[x][1],l,r);
            left_rot(x,l,r);
        } else return ;
    }
    maintain(ch[x][0],0,l,r);
    maintain(ch[x][1],1,l,r);
}
void insert(int &rt,LL l,LL r){
	LL mid=(r+l)>>1;
	if(!rt){rt=cnt;rk[rt]=l+r;return;}
	if(cmp(cnt,rt))insert(ch[rt][0],l,mid),maintain(rt,0,l,r);
    else insert(ch[rt][1],mid,r),maintain(rt,1,l,r);
}
void insert(int v){
	cl[++cnt]=v;
	insert(root,1,1LL<<61);
}
#define R(rt) rt<<1|1
#define L(rt) rt<<1
int minn[N<<2],p[N];
void build(int rt,int l,int r){
	if(l==r)read(p[l]),minn[rt]=l;
	else{
		int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
		build(lc,l,mid);
		build(rc,mid+1,r);
		minn[rt]=rk[p[minn[lc]]]<=rk[p[minn[rc]]]?minn[lc]:minn[rc];
	}
}
void updata(int rt,int l,int r,int id){
	if(l==r)return;
	int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
	if(id<=mid)updata(lc,l,mid,id);
	else updata(rc,mid+1,r,id);
	minn[rt]=rk[p[minn[lc]]]<=rk[p[minn[rc]]]?minn[lc]:minn[rc];
}
int query(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return minn[rt];
	int mid=(l+r)>>1,lc=L(rt),rc=R(rt);
	if(qr<=mid)return query(lc,l,mid,ql,qr);
	if(ql>mid)return query(rc,mid+1,r,ql,qr);
	int vl=query(lc,l,mid,ql,qr),vr=query(rc,mid+1,r,ql,qr);
	return rk[p[vl]]<=rk[p[vr]]?vl:vr;
}
char s[N],cmd[5];
int main(){
	read(n),read(m),read(len),read(type);
	scanf("%s",s);
	for(register int i=1;i<=len;i++)
		insert(s[len-i]-'a');
	build(1,1,n);
	while(m--){
		scanf("%s",cmd);
		if(!type)lastans=0;
		if(cmd[0]=='I')
			read(x),insert(x^lastans),++len;
		else if(cmd[0]=='C')
			read(x),read(p[x]),updata(1,1,n,x);
		else
			read(x),read(y),
			printf("%d\n",lastans=query(1,1,n,x,y));
	}
	return 0；
}

在丽洁姐的论文中，只谈及SGT与TREAP是重量平衡树，没有说到SBT，既然如此是否存在一种可能就是。。。。丽姐忘了SBT或者不确定SBT也是?

SBT是以节点自适应平衡的，size是节点，可不可以就意味着重量呢？貌似是可行的耶。

那么接下来，我的目的也就很明确了。 这里写图片描述

隐隐，约约，咫尺间

首先引入比较任意两个点之间的rank值的方法： 1.当然是hash了啊！！！\(O(log_n)\) 2.然后是论文中提到的序列排序方式，暴力重建子节点。期望\(O(1)\)

首先是一个大问题，（但其实也不是问题），那就是如何提取sa与rank，进而得到height。 既然是平衡树，首先应该想到的肯定是中序遍历，这里应该注意的是我们一开始insert的时候是倒序插入的，所以在提取的时候要反过来，具体代码如下：（rk数组不是rank数组，应为rk是用来动态\(O(1)\)比较大小，而不是用来作为真正的rank。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SA(int rt){
	if(!rt)return;
	SA(ch[rt][0]);
	for(register int i=0;i<=w[rt];++i)
		sa[t]=len-rt-i,rank[len-rt-i]=t++;
	SA(ch[rt][1]);
}
void make_height(){
    for(register int i=0;i<len;++i){  
        if(!rank[i]) continue;  
        int j=sa[rank[i]-1];  
        if(k)k--;  
        while(s[i+k]==s[j+k])++k;  
        height[rank[i]]=k;  
    }
}

这样就可以\(O(n)\)实现获得后缀数组。非常优秀。 仿佛已经可以看见SBT在向我挥手了。

这里写图片描述

红红火火，恍恍惚惚

tyvj的后缀数组太毒了，hzwer学长的代码都超时了，更何况常数更大的平衡树?所以我选择死亡uoj后缀排序来进行测试。

这里写图片描述 可以看见SBT在这一mol多的q下GG了，大量的旋转导致了我的SBT完美TLE。。 那么运用cnt记录连续的字母呢？ 就像这样： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert(int v){
	++cnt;
	if(cl[tot]==v){
		++w[tot];
	}else{
		tot=cnt;
		cl[cnt]=v;
		insert(root,1,1LL<<61);
	}
}
void SA(int rt){
	if(!rt)return;
	SA(ch[rt][0]);
	for(register int i=0;i<=w[rt];++i)
		sa[t]=len-rt-i,rank[len-rt-i]=t++;
	SA(ch[rt][1]);
}

然后。。。。

这里写图片描述 就这样WA了。

然而treap稳健地过了。。。泪目。。。。。 这里写图片描述

山长水阔知何处？

事实证明sbt不行（如果可以请务必告诉我！！！） 而treap的时间复杂度又太高，后缀平衡树真的就永无翻身之日？ 实则不然，后缀平衡树有着在动态与可持久化上绝对的优势，对于删除、可持久化操作，后缀平衡树不可替代。 那么最大的问题就是如何降低由于重建size的l与r而引起的常数。 1.treap的优化，详见我的 最强平衡树以及平衡树归纳 2.指针改数组加速，register，递归转递推。 3.用SGT替代treap，SGT的理论常数比treap小很多。 4.离线，用笛卡尔建树方法，O(n)建树。

三十年河东三十年河西

虽然sbt不是后缀平衡树，后缀平衡树现在也不能完全取代后缀数组，后缀自动机在很多方面也可以碾压平衡树然而它是一颗冉冉升起的红星，给予了后缀新的可能性。 今后的路需要在座的各位一起去开辟。 这里写图片描述

click it and link me

Launch CodeCogs Equation Editor