• 欢迎光临~
> > SBST及其全家桶

SBST及其全家桶

开发技术 开发技术 2022-12-31 次浏览

浅谈无用数据结构——SBST

前言

什么是 SBST 呢？其实就是 Static Binary Search Tree（静态二叉查找树）的首字母缩写，因此读的时候可以读成 S——BST (雾

其实你读到上面就大概能明白这个我瞎yy的数据结构有什么用了，SBST可以在同等时间复杂度内代替所有线段树可以做的操作

优点：作为静态的平衡树，其拥有常数较小，空间复杂度度为线段树的二分之一或四分之一（取决于建树方式），而且可以较简便维护一些线段树较难维护（不是不行，蒟蒻没有想出来不能的例子）特殊操作，相较于平衡树而言，支持合并和分裂（splay可以）

缺点：相较平衡树不支持动态的平衡插入删除，不能作翻转，相较线段树每个节点需要单独维护此节点的值

因此可以将 SBST 看做一种特殊的线段树，其介于线段树和平衡树之间

建议先学会线段树和至少一种平衡树再阅读此文

文章较晦涩，不保证所有人都能学会
实在是懒得画图了

正片

基本实现

以线段树 1 为例

规定一下数组的意义，
siz[] 子树大小
son[][2] 儿子，0 为左，1 为右
tag[] now 的标记
cnt[] 当前节点在原序列上对应位置的值
sum[] 子树值总和
N 序列长度
a[] 原序列

函数：

pushup

inline void pushup(int x){
	sum[x]=cnt[x];
	if((x<<1)<=n)sum[x]+=sum[x<<1];
	if(((x<<1)|1)<=n)sum[x]+=sum[(x<<1)|1];
}

pushdown

inline void pushdown(int x){
	if(!tag[x]) return ;
	if((x<<1)<=n)//有左儿子
		tag[x<<1]+=tag[x],sum[x<<1]+=tag[x]*siz[x<<1],cnt[x<<1]+=tag[x];
	if(((x<<1)|1)<=n)//有右儿子
		tag[(x<<1)|1]+=tag[x],sum[(x<<1)|1]+=tag[x]*siz[(x<<1)|1],cnt[(x<<1)|1]+=tag[x];
	tag[x]=0;
}

size函数，主要是为了防止查左右子树大小的时候越界

inline int size(int xx){
	return (xx<=n)?siz[xx]:0;
}

建树

建树有两种方式，堆式建树和动态开点
所谓堆式建树，是将整个 SBST 建成一个堆（完全二叉树），这样可以有效保障只需要一个 N 的空间
线段树也可以使用这种方法优化到 N*2 的空间
先直接放建树代码

inline void build(int k,int now){
	ll p=size(now<<1);
	cnt[now]=a[k+p],sum[now]=cnt[now];
	if((now<<1)<=n) build(k,now<<1);
	if(((now<<1)|1)<=n) build(k+p+1,(now<<1)|1);
	pushup(now); 
}
for(int i=n;i>1;--i) siz[(i>>1)]+=siz[i];
build(1,1);

我们这里维护堆式建树的siz，利用其来完成建树

动态开点和正常的平衡树很像，只是我们这里需要多维护一个fsiz[],用来装这个子树装满节点时的节点个数

修改

和线段树很像

想象一下，我们拿出两个点 l , r ,从根节点开始向下走

一开始，这两个节点可能会一起掉到同一个方向里一起走一段时间，
但如果有一个不走了或者进了不同的子树，他们就会分叉，不再相遇

这时我们直接让两个点一直往下走，对于 l ，其如果向左走，就把当前节点和其的左子树打上 tag ，对于 r , 同理

这里注意，如果查的 l,r 包含整个子树，直接加入答案退出即可，而且我们当前经过的节点如果被区间包含，应当直接更新cnt

代码：

inline void modify(int l,int r,ll k,int now){
	if(r-l+1==siz[now]) {
		tag[now]+=k,sum[now]+=k*siz[now],cnt[now]+=k;
		return ;
	}
	pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) cnt[now]+=k;
	if(l<=p) modify(l,min(p,r),k,now<<1);
	if(r>p+1) modify(max(1,l-p-1),r-p-1,k,(now<<1)|1);
	pushup(now);
}

查询

其实和修改同理……

pushdown 的时候记得下推到儿子的 cnt 上去

代码：

inline ll query(int l,int r,int now){
	ll s=0;
	if(r-l+1==siz[now]) return sum[now];
	pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) s+=cnt[now];
	if(l<=p) s+=query(l,min(p,r),now<<1);
	if(r>p+1) s+=query(max(1,l-p-1),r-p-1,(now<<1)|1);
	return s;
}

code

#include <iostream>
#define ll long long

using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');return;}

const int maxN=1e5+10;
int siz[maxN];
ll sum[maxN],cnt[maxN],tag[maxN],a[maxN];
int n,m;

inline int size(int xx){
	return (xx<=n)?siz[xx]:0;
} 

inline void pushdown(int x){
	if(!tag[x]) return ;
	if((x<<1)<=n)
		tag[x<<1]+=tag[x],sum[x<<1]+=tag[x]*siz[x<<1],cnt[x<<1]+=tag[x];
	if(((x<<1)|1)<=n)
		tag[(x<<1)|1]+=tag[x],sum[(x<<1)|1]+=tag[x]*siz[(x<<1)|1],cnt[(x<<1)|1]+=tag[x];
	tag[x]=0;
}

inline void pushup(int x){
	sum[x]=cnt[x];
	if((x<<1)<=n)sum[x]+=sum[x<<1];
	if(((x<<1)|1)<=n)sum[x]+=sum[(x<<1)|1];
}

inline void build(int k,int now){
	ll p=size(now<<1);
	cnt[now]=a[k+p],sum[now]=cnt[now];
	if((now<<1)<=n) build(k,now<<1);
	if(((now<<1)|1)<=n) build(k+p+1,(now<<1)|1);
	pushup(now); 
}

inline ll query(int l,int r,int now){
	ll s=0;
	if(r-l+1==siz[now]) return sum[now];
	if(size(now<<1))pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) s+=cnt[now];
	if(l<=p) s+=query(l,min(p,r),now<<1);
	if(r>p+1) s+=query(max(1,l-p-1),r-p-1,(now<<1)|1);
	return s;
}

inline void modify(int l,int r,ll k,int now){
	if(r-l+1==siz[now]) {
		tag[now]+=k,sum[now]+=k*siz[now],cnt[now]+=k;
		return ;
	}
	if(size(now<<1))pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) cnt[now]+=k;
	if(l<=p) modify(l,min(p,r),k,now<<1);
	if(r>p+1) modify(max(1,l-p-1),r-p-1,k,(now<<1)|1);
	pushup(now);
}

signed main(){
	n=read();m=read();
	for(int i=1;i<=n;++i)
		a[i]=read(),++siz[i];
	for(int i=n;i>1;--i) siz[(i>>1)]+=siz[i];
	build(1,1);
	int s,l,r;
	ll k;
	while(m--){
		s=read(),l=read(),r=read();
		if(s==1) k=read(),modify(l,r,k,1);
		else write(query(l,r,1)),putchar('n');
	}
	return 114514-114514;
}

对比分析

线段树：
SBST及其全家桶
SBST:
SBST及其全家桶
树状数组：
SBST及其全家桶

这里可以明显看出来，SBST的常数是比线段树小一些的，但依然会被树状数组干爆，由于我不会 ZKW 所以不做测试，但可以用dalao的测试结果来做个参考

其实 SBST 的优化还是在空间方面，有很大差距

SBST全家桶

线段树2

注意下推标记的时候推到cnt上

#include <iostream>
#define ll long long

using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');return;}

const int maxN=1e5+10;
int siz[maxN];
ll sum[maxN],cnt[maxN],tag[maxN],a[maxN],mu[maxN];
int n,m,p;

inline int size(int xx){
	return (xx<=n)?siz[xx]:0;
} 

inline void pushdown(int x){
	if(!tag[x]&&mu[x]==1) return ;
	if((x<<1)<=n){
		tag[x<<1]=(tag[x<<1]*mu[x])%p,tag[x<<1]=(tag[x]+tag[x<<1])%p;
		sum[x<<1]=(sum[x<<1]*mu[x])%p,sum[x<<1]=(sum[x<<1]+tag[x]*siz[x<<1])%p;
		cnt[x<<1]=(cnt[x<<1]*mu[x])%p,cnt[x<<1]=(tag[x]+cnt[x<<1])%p;
		mu[x<<1]=(mu[x]*mu[x<<1])%p;
	}
	if(((x<<1)|1)<=n){
		tag[(x<<1)|1]=(tag[(x<<1)|1]*mu[x])%p,tag[(x<<1)|1]=(tag[x]+tag[(x<<1)|1])%p; 
		sum[(x<<1)|1]=(sum[(x<<1)|1]*mu[x])%p,sum[(x<<1)|1]=(sum[(x<<1)|1]+tag[x]*siz[(x<<1)|1])%p;
		cnt[(x<<1)|1]=(cnt[(x<<1)|1]*mu[x])%p,cnt[(x<<1)|1]=(tag[x]+cnt[(x<<1)|1])%p;
		mu[(x<<1)|1]=(mu[x]*mu[(x<<1)|1])%p;
	}
	tag[x]=0,mu[x]=1;
}

inline void pushup(int x){
	sum[x]=cnt[x];
	if((x<<1)<=n)sum[x]=(sum[x<<1]+sum[x])%p;
	if(((x<<1)|1)<=n)sum[x]=(sum[x]+sum[(x<<1)|1])%p;
}

inline void build(int k,int now){
	ll p=size(now<<1);
	cnt[now]=a[k+p],sum[now]=cnt[now];
	if((now<<1)<=n) build(k,now<<1);
	if(((now<<1)|1)<=n) build(k+p+1,(now<<1)|1);
	pushup(now);
}

inline ll query(int l,int r,int now){
	ll s=0;int mod=p;
	if(r-l+1==siz[now]) return sum[now];
	if(size(now<<1))pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) s+=cnt[now];
	if(l<=p) s=(s+query(l,min(p,r),now<<1))%mod;
	if(r>p+1) s=(s+query(max(1,l-p-1),r-p-1,(now<<1)|1))%mod;
	return s;
}

inline void modify(int l,int r,ll k,int now){
	int mod=p;
	if(r-l+1==siz[now]) {
		tag[now]=(k+tag[now])%mod,sum[now]=(sum[now]+k*siz[now])%mod,cnt[now]=(cnt[now]+k)%mod;
		return ;
	}
	if(size(now<<1))pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) cnt[now]=(cnt[now]+k)%mod;
	if(l<=p) modify(l,min(p,r),k,now<<1);
	if(r>p+1) modify(max(1,l-p-1),r-p-1,k,(now<<1)|1);
	pushup(now);
}

inline void mul(int l,int r,ll k,int now){
	int mod=p;
	if(r-l+1==siz[now]) {
		tag[now]=(tag[now]*k)%mod,sum[now]=(sum[now]*k)%mod,cnt[now]=(k*cnt[now])%mod,mu[now]=(mu[now]*k)%mod;
		return ;
	}
	if(size(now<<1))pushdown(now);
	int p=size(now<<1);
	if((l<=p+1)&&(r>=p+1)) cnt[now]=(k*cnt[now])%mod;
	if(l<=p) mul(l,min(p,r),k,now<<1);
	if(r>p+1) mul(max(1,l-p-1),r-p-1,k,(now<<1)|1);
	pushup(now);
}

signed main(){
	n=read();m=read();p=read(); 
	for(int i=1;i<=n;++i)
		a[i]=(read())%p,++siz[i],mu[i]=1;
	for(int i=n;i>1;--i) siz[(i>>1)]+=siz[i];
	build(1,1);
	int s,l,r;
	ll k;
	while(m--){
		s=read(),l=read(),r=read();
		if(s==2) k=read(),modify(l,r,k,1);
		else if(s==1) k=read(),mul(l,r,k,1); 
		else write(query(l,r,1)),putchar('n');
	}
	return 114514-114514;
}
可持久化

这里就是一个动态开点的问题

代码先鸽一下

吉老师线段树

和普通线段树同理

鸽

猫树

这个就需要加一些特判了，我们可以把当前节点的值先和右子树合并，再和左子树合并，其他的使用线段树维护区间问题也可以这么做

鸽

兔树

不会，不过大体上应该是同理

合并分裂

与线段树同理，使用动态开点
推荐一篇证明合并复杂度的 Blog

鸽

程序员灯塔
转载请注明原文链接：SBST及其全家桶
喜欢 (0)