专栏文章

¿ 你说你用什么过了平衡树

UUnaccepted_Zhou
算法·理论参与者 14已保存评论 18

文章操作

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

当前评论
18 条
当前快照
1 份
快照标识符
@mlia787c
此快照首次捕获于
2026/02/12 01:06
上周
此快照最后确认于
2026/02/19 01:15
10 小时前
查看原文
ps：
本题不只有树状数组和【模板】普通平衡树。
思维难度为入门级。
前置芝士：树状数组。
我们知道它支持单点修改，前缀查询。懒标记搞不了，逆运算搞不了，复杂操作搞不了……所以树状数组有啥用？
答：逆天的码量和广泛的应用范围。码量和暴力接近，而很多题都只需要单点修改和前缀查询。
考虑维护差分序列。
0.47kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
ll c[N],n,m,o,x,y,k;
void upd(ll x,ll k)
{for(ll i=x;i<=n;i+=i&-i) c[i]+=k;}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)
	scanf("%lld",&x),upd(i,x-y),y=x;
	for(ll i=1;i<=m;i++){
		scanf"%lld%lld",&o,&x);
		if(o==1){
			scanf("%lld%lld",&y,&k);
			upd(x,k),upd(y+1,-k);
		}else{
			o=0;
			for(ll i=x;i;i-=i&-i) o+=c[i];
			printf("%lld\n",o);
		}
	}
	return 0;
}
维护差分序列，查询前缀为 r,r−1,...,1r,r-1,...,1 系数。考虑维护原树状数组和系数 n,n−1,...,n−r+1n,n-1,...,n-r+1 的树状数组拼接。
0.55kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll a[N],b[N],n,m,o,x,y;
ll q(ll x){
	ll s=0;
	for(ll i=x;i;i-=i&-i)
	s+=b[i]-a[i]*(n-x);
	return s; 
}
void u(ll x,ll k){
	for(ll i=x;i<=n;i+=i&-i)
	a[i]+=k,b[i]+=(n-x+1)*k;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&x);
		u(i,x-y),y=x;
	}
	while(m--){
		scanf("%lld",&o);
		scanf("%lld%lld",&x,&y);
		if(o==1){
			scanf("%lld",&o);
			u(x,o),u(y+1,-o);
		}else{
			ll t=q(y)-q(x-1);
			printf("%lld\n",t);
		}
	}
	return 0;
}
  • 例 33（Green）：维护 10410^4 大小，值域 ±109±10^9 的（不可重）集合，支持插入，排名和原数相互对应，前后继。
点击输入文本，直接暴力。不行用 bitset 卡常。
0.79kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+10;
ll o[N],x[N],b[N],n,m,y;
bitset<N> a,A;
ll ct(ll x){
	bitset<N> B=A>>N-x-1;
	return (a&B).count();
}
ll nm(ll x){
	ll s=0;
	for(ll i=1;i<=x;i++){
		s+=a[i];
		if(s>=x) return i;
	}
}
int main(){
	scanf("%lld",&m);
	b[++n]=2147483647,b[++n]=-b[1];
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&o[i],&x[i]);
		b[++n]=x[i];
	}
	sort(b+1,b+n+1),A.set();
	n=unique(b+1,b+n+1)-b-1;
	a[1]=a[n]=1; 
	for(ll i=1;i<=m;i++){
		if(o[i]==2) y=nm(x[i]+1);
		else{
			x[i]=upper_bound(b+1,b+n+1,x[i])-b-1;
			if(o[i]==5) a[x[i]]=1;
			else if(o[i]==1) y=ct(x[i]-1);
			else if(o[i]==3) y=nm(ct(x[i]-1));
			else if(o[i]==4) y=nm(ct(x[i])+1);
		}
		if(o[i]!=5&&o[i]!=1) y=b[y];
		if(o[i]<5) printf("%lld\n",y);
	}
	return 0;
}
引入：树状数组倍增/二分
前继：查询 <x<x 的个数 kk，然后找排名为 kk 的数。
后继：查询 ≤x\le x 的个数 kk，然后找排名为 k+1k+1 的数。
考虑权值树状数组，元素找排名为前缀查询，排名找元素为树状数组倍增/二分。
0.66kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll k=1e7+5,N=k<<1;
ll a[N],n,o,x;
ll ct(ll x){
    ll s=0;
    for(ll i=x+k;i;i-=i&-i)
    s+=a[i]; return s;
}
ll nm(ll x){
    ll s=0;
    for(ll i=24;i>=0;i--)
    if(s+(1<<i)<N&&a[s+(1<<i)]<x)
    s+=1<<i,x-=a[s]; return s+1-k;
}
int main(){
    scanf("%lld",&n);
    while(n--){
        scanf("%lld%lld",&o,&x);
        if(o<3)
        for(ll i=x+k;i<N;i+=i&-i)
        o==2?a[i]--:a[i]++;
        else if(o==3) x=ct(x-1)+1;
        else if(o==4) x=nm(x);
        else if(o==5) x=nm(ct(x-1));
        else x=nm(ct(x)+1);
        if(o>2) printf("%lld\n",x);
    }
    return 0;
}
  • 例 55（Blue）：例 33，大小 10610^6，值域 ±109±10^9，强制在线。
无法离散化，unordered_map 套树状数组暴力搞拿下 6s 佳绩。
于是乎，动态开点线段树维护。
点击输入文本。看来还需要空间卡到 128MB
1.02kCPP
#include<bits/stdc++.h>
#define k (l+r>>1)
using namespace std;
typedef int ll;
const ll N=3e7+10,V=(1<<30)-1;
ll p[N],L[N],R[N];
ll n,m,o,x,y,K=1,z,c=1,F;
ll b(ll &x){return x?x:x=++c;}
void d(ll u,ll l,ll r){
    if(r==1) F++;
    if(l==r){p[u]+=K; return;}
    if(x<=k) d(b(L[u]),l,k);
    else d(b(R[u]),k+1,r);
    p[u]=p[L[u]]+p[R[u]];
}
ll q(ll u,ll l,ll r){
    if(!u) return 0; ll s=0;
    if(r<=x) return p[u];
    if(k<x) s=q(R[u],k+1,r);
    return s+q(L[u],l,k);
}
ll f(ll u,ll l,ll r){
    if(l==r) return l;
    if(x<=p[L[u]])
    return f(L[u],l,k);
    x-=p[L[u]];
    return f(R[u],k+1,r);
}
ll ct(ll t)
{x=t; return q(1,0,V);}
ll nm(ll t)
{x=t; return f(1,0,V);}
int main(){
    scanf("%d%d",&n,&m);
    while(n--)
    scanf("%d",&x),d(1,0,V);
    while(m--){
        scanf("%d%d",&o,&x),x^=y;
        if(o<3) K=o==2?-1:1,d(1,0,V);
        else if(o==3) y=ct(x-1)+1;
        else if(o==4) y=nm(x);
        else if(o==5) y=nm(ct(x-1));
        else y=nm(ct(x)+1);
        if(o>2) z^=y;
    }
    printf("%d",z);
    return 0;
}
  • 例 66（Blue）：数组操作，每次操作完视为一个版本，每次操作基于一个历史版本后操作。
考虑版本的更新构成了一颗树，离线，进入子树操作，退出子树撤销（记录原有的值）。
局限性：不可强制在线，必须可以撤销，不能同时处理多个版本。
0.56kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
vector<ll> e[N]; ll n,m,w;
ll p[N],c[N],a[N],s[N],o;
void dfs(ll i){
	ll t=a[p[i]];
	c[i]>1.5e9?s[i]=t:a[p[i]]=c[i];
	for(auto j:e[i]) dfs(j);
	a[p[i]]=t;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) 
	scanf("%lld",&a[i]); 
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&w,&o);
		scanf("%lld",&p[i]);
		e[w].push_back(i);
		if(o==2) c[i]=2e9;
		else scanf("%lld",&c[i]);
	}
	dfs(0);
	for(ll i=1;i<=m;i++)
	if(c[i]>1.5e9)
	printf("%lld\n",s[i]);
	return 0;
}
建离线版本树（我起的名字，应该叫啥，问），按秩合并可撤销并查集即可。
1.01kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,M=N<<1;
vector<ll> a[M]; ll n,m,k;
ll d[N],s[N],o[M],x[M],y[M];
ll f(ll x){return d[x]?f(d[x]):x;}
void dfs(ll i){
	if(o[i]==1){
		ll X=f(x[i]),Y=f(y[i]);
		if(X==Y) x[i]=y[i]=0;
		else{
			if(s[X]>s[Y]) swap(X,Y);
			x[i]=X,y[i]=Y;
			s[Y]+=s[X],d[X]=Y;
		}
	}else if(o[i]==3)
	x[i]=f(x[i])==f(y[i]);
	for(auto j:a[i]) dfs(j);
	if(o[i]==1)
	s[y[i]]-=s[x[i]],d[x[i]]=0;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&o[i],&x[i]);
		o[i]==2?k=x[i]:scanf("%lld",&y[i]);
		a[k].push_back(i),k=i;
	}
	for(ll i=1;i<=n;i++) s[i]=1; dfs(0);
	for(ll i=1;i<=m;i++) if(o[i]==3)
	printf("%lld\n",x[i]);
	return 0;
}
  • 例 88（Purple）：例 44 版本板，5×1055\times10^5 个元素，值域 ±109±10^9。
离散化值域，建离线版本树，同例 55。
1.01kCPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
vector<ll> a[N];
ll c[N],o[N],v[N],b[N],n=2,m,x;
void u(ll x,ll k)
{for(ll i=x;i<=n;i+=i&-i) c[i]+=k;}
ll t(ll x){
	ll s=0;
	for(ll i=x;i;i-=i&-i) s+=c[i];
	return s;
}
ll w(ll x){
	ll s=0;
	for(ll i=1<<19;i;i>>=1)
	if(s+i<=n&&c[s+i]<x) x-=c[s+=i];
	return s+1;
}
void dfs(ll i){
	ll y=0;
	if(o[i]==4) v[i]=w(v[i]+1);
	else{
		v[i]=lower_bound(b+1,b+n+1,v[i])-b;
		if(o[i]==1) u(v[i],1);
		if(o[i]==2&&t(v[i])-t(v[i]-1))
		y=1,u(v[i],-1);
		if(o[i]==3) v[i]=t(v[i]-1);
		if(o[i]==5) v[i]=w(t(v[i]-1));
		if(o[i]==6) v[i]=w(t(v[i])+1);
	}
	if(o[i]>3) v[i]=b[v[i]]; 
	for(auto j:a[i]) dfs(j);
	if(o[i]==1) u(v[i],-1);
	if(o[i]==2) u(v[i],y);
}
int main(){
	scanf("%lld",&m);
	b[1]=-1ll<<31,b[2]=-b[1];
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&x,&o[i]);
		scanf("%lld",&v[i]);
		a[x].push_back(i),b[++n]=v[i];
	}
	sort(b+1,b+n+1);
	n=unique(b+1,b+n+1)-b-1;
	u(1,1),u(n,1),dfs(0);
	for(ll i=1;i<=m;i++) if(o[i]>2) 
	printf("%lld\n",v[i]);
	return 0;
}
  • 例 99（Purple）：给定序列，支持序列单点修改，查询区间同例 44 操作。
树状数组套树状数组，unordered_map 维护，时间复杂度 O(nlog⁡3n)O(n\log^3n)。需要访问 unordered_map 时判断 count() 卡常。
可以树状数组套动态开点线段树做到标算。
1.06kCPP
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=5e4+10,K=1e8+10;
const ll M=(-1ll<<31)+1;
unordered_map<ll,ll> b[N];
ll h[N],n,m,o,l,r,k,y;
ll a(ll x,ll y)
{return b[x].count(y)?b[x][y]:0;}
void ud(ll x,ll y,ll k){
    for(ll i=x;i<=n;i+=i&-i)
    for(ll j=y+1;j<=K;j+=j&-j)
	b[i][j]+=k;
}
ll ct(ll l,ll r,ll k){
	ll s=0;
	for(ll j=k+1;j;j-=j&-j){
		for(ll i=r;i;i-=i&-i)
		s+=a(i,j);
		for(ll i=l-1;i;i-=i&-i)
		s-=a(i,j);
	}
	return s;
}
ll nm(ll l,ll r,ll k){
	if(!k) return M; ll s=0;
	for(ll j=1<<26;j;j>>=1){
		ll t=s+j,f=0;
		if(t>1e8) continue;
		for(ll i=r;i;i-=i&-i)
		f+=a(i,t);
		for(ll i=l-1;i;i-=i&-i)
		f-=a(i,t);
		if(f<k) k-=f,s=t;
	}
	return k>1e8+5?-M:s;
}
int main(){
	scanf("%d%d",&n,&m);
	for(ll i=1;i<=n;i++)
	scanf("%d",&h[i]),ud(i,h[i],1); 
	while(m--){
		scanf("%d%d",&o,&l);
		if(o!=3) scanf("%d",&r);
		scanf("%d",&k);
		if(o==1) y=ct(l,r,k-1)+1;
		if(o==2) y=nm(l,r,k);
		if(o==3) ud(l,h[l],-1),
		ud(l,h[l]=k,1);
		if(o==4)
		y=nm(l,r,ct(l,r,k-1));
		if(o==5)
		y=nm(l,r,ct(l,r,k)+1);
		if(o!=3) printf("%d\n",y);
	}
    return 0;
}
1.45k O(nlog⁡2n)O(n\log^2n)
实测快 33 倍。
CPP
#include<bits/stdc++.h>
#define f (l+r>>1)
using namespace std;
typedef int ll;
const ll N=5e4+10,M=3e7+10;
const ll V=1e8+1,K=(-1<<31)+1;
struct D{ll u,k;}; ll x,y,c,l,r;
ll p[M],L[M],R[M],b[N],n,m,o,k,z;
ll g(ll &x){return x?x:x=++c;}
void d(ll u,ll l,ll r){
	if(l==r){p[u]+=k; return;}
	if(x<=f) d(g(L[u]),l,f);
	else d(g(R[u]),f+1,r);
	p[u]=p[L[u]]+p[R[u]];
}
ll q(ll u,ll l,ll r){
	if(!u) return 0;
	if(r<=x) return p[u];
	ll s=q(L[u],l,f);
	if(f<x) s+=q(R[u],f+1,r); 
	return s;
}
ll h(vector<D> u,ll l,ll r){
	if(l==r) return l==V?-K:l;
	vector<D> _l,_r; ll t=0;
	for(auto v:u){
		_l.push_back({L[v.u],v.k});
		_r.push_back({R[v.u],v.k});
		t+=p[L[v.u]]*v.k;
	}
	if(k<=t) return h(_l,l,f);
	k-=t; return h(_r,f+1,r);
}
void ud(ll a,ll b,ll c){
	for(ll i=a;i<=n;i+=i&-i)
	x=b,k=c,d(i,0,V);
}
ll ct(ll l,ll r,ll c){
	ll s=0; x=c;
	for(ll i=r;i;i-=i&-i)
	s+=q(i,0,V);
	for(ll i=l-1;i;i-=i&-i)
	s-=q(i,0,V);
	return s;
}
ll nm(ll l,ll r,ll c){
	if(!c) return K;
	k=c; vector<D> u;
	for(ll i=r;i;i-=i&-i)
	u.push_back({i,1});
	for(ll i=l-1;i;i-=i&-i)
	u.push_back({i,-1});
	return h(u,0,V);
}
int main(){
	scanf("%d%d",&n,&m),c=n;//`c
	for(ll i=1;i<=n;i++)
	scanf("%d",&b[i]),ud(i,b[i],1);
	while(m--){
		scanf("%d%d",&o,&l);
		if(o!=3) scanf("%d",&r);
		scanf("%d",&z);
		if(o==1) z=ct(l,r,z-1)+1;
		if(o==2) z=nm(l,r,z);
		if(o==3) ud(l,b[l],-1),
		ud(l,b[l]=z,1);
		if(o==4)
		z=nm(l,r,ct(l,r,z-1));
		if(o==5)
		z=nm(l,r,ct(l,r,z)+1);
		if(o!=3) printf("%d\n",z);
	}
	return 0;
}
总结：
一本正经地扯神秘做法。
鉴于局限性，请大家认真学习正常数据结构的同时，善于使用以上或 STL 简化代码，别上来就各种数据结构乱上。

评论

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

正在加载评论...