?你说你用什么过了平衡树
Unaccepted_Zhou · · 算法·理论
ps：
本题不只有树状数组和【模板】普通平衡树。
思维难度为入门级。
前置芝士：树状数组。
我们知道它支持单点修改，前缀查询。懒标记搞不了，逆运算搞不了，复杂操作搞不了……所以树状数组有啥用？
答：逆天的码量和广泛的应用范围。码量和暴力接近，而很多题都只需要单点修改和前缀查询。
- 例
1 （Green）：区间修改，单点查询
考虑维护差分序列。
:::success[0.47k]
#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;
}
:::
- [例 $2$（Green）](https://www.luogu.com.cn/problem/P3372)：区间修改，区间查询
维护差分序列，查询前缀为 $r,r-1,...,1$ 系数。考虑维护原树状数组和系数 $n,n-1,...,n-r+1$ 的树状数组拼接。
:::success[0.55k]
```cpp
#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;
}
:::
- [例 $3$（Green）](https://www.luogu.com.cn/problem/P5076)：维护 $10^4$ 大小，值域 $±10^9$ 的（不可重）集合，支持插入，排名和原数相互对应，前后继。
点击输入文本，直接暴力。不行用 `bitset` 卡常。
:::success[0.79k]
```cpp
#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;
}
:::
---
[引入：树状数组倍增/二分](https://www.luogu.com.cn/article/klof1kp5)
---
- [例 $4$（Blue）](https://www.luogu.com.cn/problem/P3369)：例 $3$，大小 $10^5$，值域 $±10^7$。
前继：查询 $<x$ 的个数 $k$，然后找排名为 $k$ 的数。
后继：查询 $\le x$ 的个数 $k$，然后找排名为 $k+1$ 的数。
考虑权值树状数组，元素找排名为前缀查询，排名找元素为树状数组倍增/二分。
:::success[0.66k]
```cpp
#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;
}
:::
- [例 $5$（Blue）](https://www.luogu.com.cn/problem/P6136)：例 $3$，大小 $10^6$，值域 $±10^9$，强制在线。
无法离散化，`unordered_map` 套树状数组暴力搞拿下 6s 佳绩。
于是乎，动态开点线段树维护。
点击输入文本。~~看来还需要空间卡到 128MB~~
:::success[1.02k]
```cpp
#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;
}
:::
- [例 $6$（Blue）](https://www.luogu.com.cn/problem/P3919)：数组操作，每次操作完视为一个版本，每次操作基于一个历史版本后操作。
考虑版本的更新构成了一颗树，离线，进入子树操作，退出子树撤销（记录原有的值）。
局限性：不可强制在线，必须可以撤销，不能同时处理多个版本。
:::success[0.56k]
```cpp
#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;
}
:::
- [例 $7$（Purple）](https://www.luogu.com.cn/problem/P3402)：版本并查集。
建离线版本树（我起的名字，应该叫啥，问），按秩合并可撤销并查集即可。
:::success[1.01k]
```cpp
#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;
}
:::
- [例 $8$（Purple）](https://www.luogu.com.cn/problem/P3835)：例 $4$ 版本板，$5\times10^5$ 个元素，值域 $±10^9$。
离散化值域，建离线版本树，同例 $5$。
:::success[1.01k]
```cpp
#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;
}
:::
- [例 $9$（Purple）](https://www.luogu.com.cn/problem/P3380)：给定序列，支持序列单点修改，查询区间同例 $4$ 操作。
树状数组套树状数组，`unordered_map` 维护，时间复杂度 $O(n\log^3n)$。需要访问 `unordered_map` 时判断 `count()` 卡常。
可以树状数组套动态开点线段树做到标算。
:::success[1.06k]
```cpp
#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;
}
:::
:::success[1.45k $O(n\log^2n)$]
实测快 $3$ 倍。
```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 简化代码，~~别上来就各种数据结构乱上。~~