¿ 树状树组替代平衡树 II

Unac_Zhou · 2026-09-08 20:52:05 · 算法·理论

前传

• 例 5（Blue）：维护 10^6 大小，值域 ±10^9 的可重集合，支持插入，排名和原数相互对应，前后继。强制在线。

线段树代码太长不想写。考虑 unordered_map.max_load_factor(0.5) 减少冲突（填的数为元素数量和哈希桶数量的比值）和 unordered_map.reserve(n)（预留 n 个元素，防止自动的重构桶）优化 umap。

而且树状树组很难减到 0，判断是否 erase() 反而劣化。

还有一个不知名优化。因为存在元素 0 树状树组显然会有一个偏移量 1。将这个 1 改成 2 会发现过了。

:::success[0.93k]

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long lll;
const ll k=2,N=k+(1<<30);
unordered_map<ll,ll>a;
ll n,m,o,x,y,z,c;
void rd(ll &x){
    x=0; while((c=getchar())<45);
    do x=c-48+x*10;
    while((c=getchar())>47);
}
void up(ll x,ll y)
{for(lll i=x+k;i<N;i+=i&-i) a[i]+=y;}
ll f(ll x)
{return a.count(x)?a[x]:0ll;}
ll ct(ll x){
    ll s=0;
    for(ll i=x+k;i;i-=i&-i)
    s+=f(i); return s;
}
ll nm(ll x){
    lll s=0;
    for(ll i=30;i>=0;i--)
    if(s+(1<<i)<N&&f(s+(1<<i))<x)
    s+=1<<i,x-=f(s); return s+1-k;
}
int main(){
    rd(n),rd(m);
    a.max_load_factor(0.8);
    a.reserve((n+m)*10);
    while(n--) rd(x),up(x,1);
    while(m--){
        rd(o),rd(x),x^=y;
        if(o<3) up(x,o==2?-1:1);
        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;
}
:::

当然还可以直接哈希表，速度起飞。

:::success[0.93k]
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long lll;
const ll k=2,K=1e7+19;
const ll N=k+(1<<30),W=4e7;
ll h[K],nx[W],g[W],w;
ll a[W],n,m,o,x,y,z,c;
ll f(ll x){
    ll &H=h[x%K];
    for(ll i=H;i;i=nx[i])
    if(g[i]==x) return i;
    g[++w]=x,nx[w]=H; return H=w;
}
void up(ll x,ll y){
    for(lll i=x+k;i<N;i+=i&-i)
    a[f(i)]+=y;
}
ll ct(ll x){
    ll s=0;
    for(ll i=x+k;i;i-=i&-i)
    s+=a[f(i)]; return s;
}
ll nm(ll x){
    lll s=0;
    for(ll i=30;i>=0;i--)
    if(s+(1<<i)<N&&a[f(s+(1<<i))]<x)
    s+=1<<i,x-=a[f(s)]; return s+1-k;
}
int main(){
    scanf("%d%d",&n,&m);
    while(n--) scanf("%d",&x),up(x,1);
    while(m--){
        scanf("%d%d",&o,&x),x^=y;
        if(o<3) up(x,o==2?-1:1);
        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;
}
:::

- [例 $9$（Purple）](https://www.luogu.com.cn/problem/P3380)：给定序列，支持序列单点修改，查询区间同例 $4$ 操作。

树状树组套树状树组，然后直接哈希表。一通操作下来一看分数 $98$。

为啥小常数 $2\log$ 过不去。为啥动开线段树常数小于哈希表。不想卡了。