浅谈压位 trie 及其简单应用

KingGojianOfYue · 2026-01-07 17:23:53 · 算法·理论

Update on 2026.1.23：修改了一些错误。

突然想写就写了。

功能

可以在 O(\log_w{V})（w 为计算机位长，通常取 32 或 64）的时间复杂度、O(\frac{V}{w}) 的空间复杂度下完成以下操作：

插入一个不存在的数或删除一个数；
查询最小或最大值；
查询前驱后继。

正常用 01trie 只能做到 O(\log_2{V})，因为它是一个 2 叉树。我们发现每个位置只用存 0/1，我们直接分 w 叉不就优完了？

实现

插入删除是好做的，查询最小最大值的话用 __builtin_ctz 和 __builtin_clz 稍微处理一下就可以了。查询前驱后继的话，跟正常的平衡树一样：我们从叶子结点往根跑，查询一下有没有比它大或小的兄弟，然后再在这里面查询最小或最大值即可。

以下是对于 V=2^{20} 的压位 trie 代码（直接展开写的，常数会小一些）：

struct trie{
    #define ctz(x) __builtin_ctz(x)
    #define clz(x) __builtin_clz(x)
    int ans;
    unsigned int a0,a1[1<<5],a2[1<<10],a3[1<<15],ak;
    inline void ins(const int x)noexcept{
        a0|=1u<<(x>>15),a1[x>>15]|=1u<<((x>>10)&31),
        a2[x>>10]|=1u<<((x>>5)&31),a3[x>>5]|=1u<<(x&31);
    }
    inline void era(const int x)noexcept{
        (a3[x>>5]&=~(1u<<(x&31)))?(1):(
            (a2[x>>10]&=~(1u<<((x>>5)&31)))?(1):(
                (a1[x>>15]&=~(1u<<((x>>10)&31)))?(1):(
                    a0&=~(1u<<(x>>15))
                )
            )
        );
    }
    inline bool have(const int x)noexcept{return (a3[x>>5]>>(x&31))&1;}
    inline int minn()noexcept{
        return a0?(ans=ctz(a0),ans=(ans<<5)|ctz(a1[ans]),ans=(ans<<5)|ctz(a2[ans]),(ans<<5)|ctz(a3[ans])):(1<<20);
    }
    inline int maxn()noexcept{
        return a0?(ans=31^clz(a0),
        ans=(ans<<5)|(31^clz(a1[ans])),
        ans=(ans<<5)|(31^clz(a2[ans])),
        (ans<<5)|(31^clz(a3[ans]))):(0);
    }
    inline int suf(const int x)noexcept{
        if((ak=(a3[x>>5]>>(x&31))>>1)){
            return(x&~31u)|((x&31)+1+ctz(ak));
        }if((ak=(a2[x>>10]>>((x>>5)&31))>>1)){
            return ans=((x>>5)&~31u)|(((x>>5)&31)+1+ctz(ak)),
            (ans<<5)|ctz(a3[ans]);
        }if((ak=(a1[x>>15]>>((x>>10)&31))>>1)){
            return ans=((x>>10)&~31u)|(((x>>10)&31)+1+ctz(ak)),
            ans=(ans<<5)|ctz(a2[ans]),(ans<<5)|ctz(a3[ans]);
        }if((ak=a0>>(x>>15)>>1)){
            return ans=((x>>15)&~31u)|(((x>>15)&31)+1+ctz(ak)),
            ans=(ans<<5)|ctz(a1[ans]),ans=(ans<<5)|ctz(a2[ans]),(ans<<5)|ctz(a3[ans]);
        }return x;
    }
    inline int pre(const int x)noexcept{
        if((ak=a3[x>>5]&((1u<<(x&31))-1))){
            return(x&~31u)|(31^clz(ak));
        }if((ak=a2[x>>10]&((1u<<((x>>5)&31))-1))){
            return ans=((x>>5)&~31u)|(31^clz(ak)),
            (ans<<5)|(31^clz(a3[ans]));
        }if((ak=a1[x>>15]&((1u<<((x>>10)&31))-1))){
            return ans=((x>>10)&~31u)|(31^clz(ak)),
            ans=(ans<<5)|(31^clz(a2[ans])),(ans<<5)|(31^clz(a3[ans]));
        }if((ak=a0&((1u<<(x>>15))-1))){
            return ans=((x>>15)&~31u)|(31^clz(ak)),
            ans=(ans<<5)|(31^clz(a1[ans])),ans=(ans<<5)|(31^clz(a2[ans])),(ans<<5)|(31^clz(a3[ans]));
        }return x;
    }
};

动态开点的话就把上面的数组改成 unordered_map 即可，空间复杂度就是 \min(n\log_wV,\frac{V}{w})。

对比

可能很多人对 O(\log_{w}{V}) 没什么概念，其实就是 O(\log_{2}{V}) 优化了 \frac{1}{5} 或 \frac{1}{6}，通常可以看成一个 4 或 5 的常数。

应用

由于题目中往往可以有重复元素，所以使用压位 trie 前经常得用离散化。

以 P3378 【模板】堆为例，可以先用基数排序让每个值互不相同然后再用压位 trie 做到 O(n\log_{w}n)：

trie t;
unsigned bucket[256];
#define SORTBYTE(TYPE, FR, TO, LEN, BIT) {\
    memset(bucket, 0, sizeof(bucket));\
    for (TYPE *it = (FR) + LEN; it != (FR); it--)\
        ++bucket[(it[-1].x >> BIT) & 255];\
    for (unsigned *it = bucket; it != bucket + 255; it++)\
        it[1] += it[0];\
    for (TYPE *it = (FR) + LEN; it != (FR); it--)\
        (TO)[--bucket[(it[-1].x >> BIT) & 255]] = it[-1];\
}
constexpr int N=1e6+5;
struct node{int id,x;}q[N],st[N],st2[N];int n,top;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>q[i].id,(q[i].id==1)?(cin>>q[i].x,st2[top++]={i,q[i].x}):(node{});
    SORTBYTE(node,st2,st,top, 0);SORTBYTE(node,st,st2,top, 8);
    SORTBYTE(node,st2,st,top,16);SORTBYTE(node,st,st2,top,24);SORTBYTE(node,st2,st,top,30);
    for(int i=0;i<top;++i)q[st[i].id].x=i;
    for(int i=1;i<=n;++i){
        switch(q[i].id){
            case 1:t.ins(q[i].x);break;
            case 2:cout<<st[t.minn()].x<<'\n';break;
            case 3:t.era(t.minn());break;
        }
    }
    return 0;
}

跑得有点慢，用了 200 多毫秒。

经常很多分块题你只能想到甚至只能做到类似于 O(n\sqrt{n\log_2n}) 的东西，用上压位 trie 你就可以强行创过去或抢到最优解（例如 P8078 [WC2022] 秃子酋长就可以拿 n\sqrt{n}\log_wn 应创，并且卡不掉）。

众所周知，正常的珂朵莉树区间赋值单点查用 set 只能在非随机数据下做到 O(n\log_2n)，但是不难发现这其实每次都是在插入删除或求前驱后继，直接上压位 trie 就可以做到 O(n\log_{w}n)（使用 Veb 可以做到严格 O(n\log_2\log_2n)）。

以 P13983数列分块入门8 为例，当其他人在使用 O(n\log_{2}n) 的 set 维护珂朵莉树时，你可以直接悄悄地交一发 O(n\log_{w}n) 的压位 trie 并成功得到最优解。

trie t;
constexpr int N=3e5+5;
int n,m;
int nxt[N],val[N],ans;
inline void split(int l)
{
    if(t.have(l))return;
    int pr=t.pre(l);t.ins(l);
    nxt[l]=nxt[pr],val[l]=val[pr],nxt[pr]=l;
}
int main(){
    cin>>n;t.ins(n+1);
    for(int i=1;i<=n;++i)nxt[i]=i+1,cin>>val[i],t.ins(i);
    int l,r,v,ll,su;
    for(int i=1;i<=n;++i){
        cin>>l>>r>>v;ans=0;
        split(ll=l),split(++r);
        do{
            (val[ll]==v)?(su=nxt[ll],t.era(su),ans+=su-ll,ll=su):(su=nxt[ll],t.era(su),ll=su);
        }while(ll!=r);
        nxt[l]=r,val[l]=v,t.ins(r);
        cout<<ans<<'\n';
    }
    return 0;
}

还有就是：两个 01trie 进行位运算的复杂度跟 bitset 复杂度是一样的，例题待补。