专栏文章

rope测试

UUnionRE
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min03djd
此快照首次捕获于
2025/12/01 18:22
3 个月前
此快照最后确认于
2025/12/01 18:22
3 个月前
查看原文

本文只测试了插入操作，其余操作时间复杂度相同

第一次非严格测试

使用学校机房，10th Gen Intel(R) Core(TM)i5 \text{10th Gen Intel(R) Core(TM)i5 }，内存 16GB16GB，后面忘了（更快）。
测试用代码
Treap
CPP
//treap
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;
int root=0,k;
struct treap{
	int ls,rs;
	int val,pri;
	int cnt,size;
}t[MAXN];
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+t[id].cnt;}
void zag(int &rt){//左旋
	int b=t[rt].rs;
	t[rt].rs=t[b].ls;
	t[b].ls=rt;
	up(rt);up(b);
	rt=b;
}
void zig(int &rt){//右旋
	int b=t[rt].ls;
	t[rt].ls=t[b].rs;
	t[b].rs=rt;
	up(rt);up(b);
	rt=b;
}
void insert(int &rt,int x){
	if(rt==0){
		t[++k].val=x;
		t[k].cnt=t[k].size=1;
		t[k].pri=rand()%1145140;
		rt=k;
		return;
	}
	t[rt].size++;
	if(x==t[rt].val){
		t[rt].cnt++;
		return;
	}
	if(x<t[rt].val){
		insert(t[rt].ls,x);
		if(t[t[rt].ls].pri<t[rt].pri)zig(rt);
	}
	else{
		insert(t[rt].rs,x);
		if(t[t[rt].rs].pri<t[rt].pri)zag(rt);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	srand(time(NULL));
	memset(t,0,sizeof(t));
	int n,opt,x;
	cin>>n;
	while(n--){
		insert(root,rand());//懒得改了，都是非严格嘛~
	}
	return 0;
}
rope
CPP
#include<bits/extc++.h>
using namespace std;
int n;
__gnu_cxx::rope<int> rp;
int main(){
	cin>>n;
	while(n--)rp.insert(rand());
	
	
	return 0;
}
由 longlong666 提供的神秘平衡树
CPP
//#include <bits/stdc++.h>
//#define int long long
#include <iostream>
#include <limits.h>
#include <random>
#include <chrono>
#define ll long long
#define endl '\n'
#define inline
#define max(a,b) (a>b?a:b)
#define F__K_CCF 0
using namespace std;
const int maxn=1e5+10;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int tr_rot,tr_cnt;bool judge=rnd()%2;
struct LAVL{int lc,rc,h,siz,cnt,val;}tr[maxn];
inline void up(int &iden){tr[iden].h=max(tr[tr[iden].lc].h,tr[tr[iden].rc].h)+1;tr[iden].siz=tr[tr[iden].lc].siz+tr[tr[iden].rc].siz+tr[iden].cnt;}
inline void left(int &iden){int rs=tr[iden].rc;tr[iden].rc=tr[rs].lc,up(iden),tr[rs].lc=iden,iden=rs,up(iden);}
inline int jsleft(int &iden){return max(max(tr[tr[iden].lc].h,tr[tr[tr[iden].rc].lc].h)+1,tr[tr[tr[iden].rc].rc].h)+1;}
inline void right(int &iden){int ls=tr[iden].lc;tr[iden].lc=tr[ls].rc,up(iden),tr[ls].rc=iden,iden=ls,up(iden);}
inline int jsright(int &iden){return max(max(tr[tr[iden].rc].h,tr[tr[tr[iden].lc].rc].h)+1,tr[tr[tr[iden].lc].lc].h)+1;}
inline void Balanced(int &iden){while(jsleft(iden)<=tr[iden].h)left(iden);while(jsright(iden)<=tr[iden].h)right(iden);}
inline int Newnode(int x){tr[++tr_cnt]={0,0,1,1,1,x};return tr_cnt;}
inline void insert(int &iden,int x){
	if(!iden){iden=Newnode(x);return;}
	++tr[iden].siz;
	if(x==tr[iden].val)++tr[iden].cnt;
	if(x<tr[iden].val)insert(tr[iden].lc,x);
	if(x>tr[iden].val)insert(tr[iden].rc,x);
	up(iden),Balanced(iden);
}
inline void erase(int &iden,int x){
	if(!iden)return;
	if(x<tr[iden].val)return--tr[iden].siz,erase(tr[iden].lc,x);
	if(x>tr[iden].val)return--tr[iden].siz,erase(tr[iden].rc,x);
	if(tr[iden].cnt>1){--tr[iden].siz,--tr[iden].cnt;return;}
	if(!tr[iden].lc||!tr[iden].rc){--tr[iden].siz,iden=tr[iden].lc+tr[iden].rc;return;}
	if(judge)--tr[iden].siz,right(iden),erase(tr[iden].rc,x);else--tr[iden].siz,left(iden),erase(tr[iden].lc,x);
	up(iden),Balanced(iden);
}
inline int get3(int iden,int x){
	if(!iden)return 1;
	if(x<tr[iden].val)return get3(tr[iden].lc,x);
	if(x==tr[iden].val)return tr[tr[iden].lc].siz+1;
	if(x>tr[iden].val)return tr[tr[iden].lc].siz+tr[iden].cnt+get3(tr[iden].rc,x);
	return F__K_CCF;
}
inline int get4(int iden,int x){
	if(x<=tr[tr[iden].lc].siz)return get4(tr[iden].lc,x);
	if(x<=tr[tr[iden].lc].siz+tr[iden].cnt)return tr[iden].val;
	return get4(tr[iden].rc,x-tr[tr[iden].lc].siz-tr[iden].cnt);
}
inline int get5(int iden,int x){
	if(!iden)return INT_MIN;
	if(x<=tr[iden].val)return get5(tr[iden].lc,x);
	if(x>tr[iden].val)return max(tr[iden].val,get5(tr[iden].rc,x));
	return F__K_CCF;
}
inline int get6(int iden,int x){
	if(!iden)return INT_MAX;
	if(x>=tr[iden].val)return get6(tr[iden].rc,x);
	if(x<tr[iden].val)return min(tr[iden].val,get6(tr[iden].lc,x));
	return F__K_CCF;
}
inline void insert(int x){insert(tr_rot,x);}
inline void erase(int x){erase(tr_rot,x);}
inline int get3(int x){return get3(tr_rot,x);}
inline int get4(int x){return get4(tr_rot,x);}
inline int get5(int x){return get5(tr_rot,x);}
inline int get6(int x){return get6(tr_rot,x);}
int q;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	while(n--)insert(rand());
	return 0;
}
longlong666 提供的 AVL
CPP
//#include <bits/stdc++.h>
//#define int long long
#include <iostream>
#include <limits.h>
#include <random>
#include <chrono>
#define ll long long
#define endl '\n'
#define inline
#define max(a,b) (a>b?a:b)
#define F__K_CCF 0
using namespace std;
const int maxn=1e5+10;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int tr_rot,tr_cnt;bool judge=rnd()%2;
struct LAVL{int lc,rc,h,siz,cnt,val;}tr[maxn];
inline void up(int &iden){tr[iden].h=max(tr[tr[iden].lc].h,tr[tr[iden].rc].h)+1;tr[iden].siz=tr[tr[iden].lc].siz+tr[tr[iden].rc].siz+tr[iden].cnt;}
inline void left(int &iden){int rs=tr[iden].rc;tr[iden].rc=tr[rs].lc,up(iden),tr[rs].lc=iden,iden=rs,up(iden);}
inline void right(int &iden){int ls=tr[iden].lc;tr[iden].lc=tr[ls].rc,up(iden),tr[ls].rc=iden,iden=ls,up(iden);}
inline void Balanced(int &iden){while(tr[tr[iden].rc].h-tr[tr[iden].lc].h>1)left(iden);while(tr[tr[iden].lc].h-tr[tr[iden].rc].h>1)right(iden);}
inline int Newnode(int x){tr[++tr_cnt]={0,0,1,1,1,x};return tr_cnt;}
inline void insert(int &iden,int x){
	if(!iden){iden=Newnode(x);return;}
	++tr[iden].siz;
	if(x==tr[iden].val)++tr[iden].cnt;
	if(x<tr[iden].val)insert(tr[iden].lc,x);
	if(x>tr[iden].val)insert(tr[iden].rc,x);
	up(iden),Balanced(iden);
}
inline void erase(int &iden,int x){
	if(!iden)return;
	if(x<tr[iden].val)return--tr[iden].siz,erase(tr[iden].lc,x);
	if(x>tr[iden].val)return--tr[iden].siz,erase(tr[iden].rc,x);
	if(tr[iden].cnt>1){--tr[iden].siz,--tr[iden].cnt;return;}
	if(!tr[iden].lc||!tr[iden].rc){--tr[iden].siz,iden=tr[iden].lc+tr[iden].rc;return;}
	if(judge)--tr[iden].siz,right(iden),erase(tr[iden].rc,x);else--tr[iden].siz,left(iden),erase(tr[iden].lc,x);
	up(iden),Balanced(iden);
}
inline int get3(int iden,int x){
	if(!iden)return 1;
	if(x<tr[iden].val)return get3(tr[iden].lc,x);
	if(x==tr[iden].val)return tr[tr[iden].lc].siz+1;
	if(x>tr[iden].val)return tr[tr[iden].lc].siz+tr[iden].cnt+get3(tr[iden].rc,x);
	return F__K_CCF;
}
inline int get4(int iden,int x){
	if(x<=tr[tr[iden].lc].siz)return get4(tr[iden].lc,x);
	if(x<=tr[tr[iden].lc].siz+tr[iden].cnt)return tr[iden].val;
	return get4(tr[iden].rc,x-tr[tr[iden].lc].siz-tr[iden].cnt);
}
inline int get5(int iden,int x){
	if(!iden)return INT_MIN;
	if(x<=tr[iden].val)return get5(tr[iden].lc,x);
	if(x>tr[iden].val)return max(tr[iden].val,get5(tr[iden].rc,x));
	return F__K_CCF;
}
inline int get6(int iden,int x){
	if(!iden)return INT_MAX;
	if(x>=tr[iden].val)return get6(tr[iden].rc,x);
	if(x<tr[iden].val)return min(tr[iden].val,get6(tr[iden].lc,x));
	return F__K_CCF;
}
inline void insert(int x){insert(tr_rot,x);}
inline void erase(int x){erase(tr_rot,x);}
inline int get3(int x){return get3(tr_rot,x);}
inline int get4(int x){return get4(tr_rot,x);}
inline int get5(int x){return get5(tr_rot,x);}
inline int get6(int x){return get6(tr_rot,x);}
int q;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	while(n--)insert(rand());
	return 0;
}

结果

代码n=105n=10^5n=5×105n=5\times 10^5n=106n=10^6n=5×106n=5\times 10^6
treap62.5ms62.5ms109.4ms109.4ms187.5ms187.5ms843ms843ms
rope453.1ms453.1ms2547ms\red{2547ms}5109ms\red{5109ms}-
神秘---3047ms3047ms
AVL---1391ms1391ms
BIT---140ms\green{140ms}
rope 是 O(n)O(\sqrt{n})的。

第二次测试

使用自己电脑，12th Gen Intel(R) Core(TM) i7-12700H (2.30 GHz) \text{12th Gen Intel(R) Core(TM) i7-12700H (2.30 GHz) }。
内存 24GB24GB。
测试用代码
申明：代码中输出时间部分是秒数，不是 ms。 sgt
CPP
//权值线段树
#include<bits/stdc++.h>
#define int long long
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int maxn=100000+10;
struct node {
	int l,r,cnt;
} tr[maxn*4];
int a[maxn],b[maxn],n,opt[maxn],tot=0,p;
inline void build(int id,int l,int r) {
	tr[id].l=l;
	tr[id].r=r;
	if(l==r) return;
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
inline void update(int id,int l,int r,int x) {
	if(tr[id].l>r || tr[id].r<l) return;
	if(tr[id].l>=l && tr[id].r<=r) {
		tr[id].cnt+=x;
		return;
	}
	update(ls,l,r,x);
	update(rs,l,r,x);
	tr[id].cnt=tr[ls].cnt+tr[rs].cnt;
}
signed main() {
    clock_t be,en;
	cin>>n;
    be=clock();
    build(1,1,39000);
	while(n--){int x=rand();update(1,x,x,1);}
    en=clock();
    cout<<((double)(en-be)/CLOCKS_PER_SEC)<<"ms"<<endl;
	return 0;
}
treap
CPP
//treap
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;
int root=0,k;
struct treap{
	int ls,rs;
	int val,pri;
	int cnt,size;
}t[MAXN];
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+t[id].cnt;}
void zag(int &rt){//左旋
	int b=t[rt].rs;
	t[rt].rs=t[b].ls;
	t[b].ls=rt;
	up(rt);up(b);
	rt=b;
}
void zig(int &rt){//右旋
	int b=t[rt].ls;
	t[rt].ls=t[b].rs;
	t[b].rs=rt;
	up(rt);up(b);
	rt=b;
}
void insert(int &rt,int x){
	if(rt==0){
		t[++k].val=x;
		t[k].cnt=t[k].size=1;
		t[k].pri=rand()%1145140;
		rt=k;
		return;
	}
	t[rt].size++;
	if(x==t[rt].val){
		t[rt].cnt++;
		return;
	}
	if(x<t[rt].val){
		insert(t[rt].ls,x);
		if(t[t[rt].ls].pri<t[rt].pri)zig(rt);
	}
	else{
		insert(t[rt].rs,x);
		if(t[t[rt].rs].pri<t[rt].pri)zag(rt);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	memset(t,0,sizeof(t));
    clock_t be,en;
	int n,opt,x;
	cin>>n;
    be=clock();
	while(n--){
		insert(root,rand());//懒得改了，后面忘了
	}
    en=clock();
    cout<<((double)(en-be)/CLOCKS_PER_SEC)<<"ms"<<endl;
	return 0;
}
fhq
CPP
//FHQ
#include<bits/stdc++.h>
using namespace std;
const signed int MAXN=200005000;
struct FHQNode{
	int ls,rs;
	int val,pri,size;
}t[MAXN];
int tot=0,root=0,n,m,opt,Fx,last=0,Tx;
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+1;return;}
void crt_node(int x){//新建
	++tot;
	t[tot].size=1;
	t[tot].ls=t[tot].rs=0;
	t[tot].val=x;
	t[tot].pri=rand();
	return;
}
void split(int u,int x,int &L,int &R){
	if(u==0){L=R=0;return;}
	if(t[u].val<=x){
		L=u;//左边确定
		split(t[u].rs,x,t[u].rs,R);
	}
	else{
		R=u;//右边确定
		split(t[u].ls,x,L,t[u].ls);
	}
	up(u);
	return;
}
int merge(int L,int R){
	if(L==0||R==0)return L+R;
	if(t[L].pri>t[R].pri){
		t[L].rs=merge(t[L].rs,R);
		up(L);
		return L;
	}
	else{
		t[R].ls=merge(L,t[R].ls);
		up(R);
		return R;
	}
}
void insert(int x){
	int L,R;
	split(root,x,L,R);
	crt_node(x);
	root=merge(merge(L,tot),R);
	return;
}
int main(){
	cin>>n;
    clock_t be,en;
    be=clock();
    while(n--){insert(rand());}
    en=clock();
    cout<<((double)(en-be)/CLOCKS_PER_SEC)<<"ms"<<endl;
	return 0;
}
rope
CPP
#include<bits/extc++.h>
using namespace std;
int n;
__gnu_cxx::rope<int> rp;
int main(){
    clock_t be,en;
	cin>>n;
    be=clock();
	while(n--)rp.insert(rand());
    en=clock();
	cout<<((double)(en-be)/CLOCKS_PER_SEC)<<"ms"<<endl;
	
	return 0;
}
代码n=106n=10^6n=5×106n=5\times 10^6
sgt162ms\green{162ms}777ms\green{777ms}
treap221ms221ms1113ms1113ms
rope5420ms\red{5420ms}85668ms\red{85668ms}
FHQ1095ms1095ms12137ms\red{12137ms}
rope 是 O(n)O(\sqrt{n})，另外 FHQ 大常数。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...