压位Trie_算法

压位Trie

能够 $\Theta(n\log_{64}V)$ 进行插入删除求前驱后继。

其实就跟它的名字一样，只不过为了快使用了很多别样的写法。

由低位向高位存储，以下代码适用于 $V<2^{24}$ 的情况，$V<2^{30}$ 时需要开到 $5$ 个数组，更大的 $V$ 由于空间爆炸无法开下，当然硬上 __int128 也不是不行。

局限性十分大，仅能用来卡常，无法像正常的平衡树一样开很多个。

typedef decltype(1ull) ull;
struct Trie {
    vector<ull> f[4];
    void init() {
        f[0]=vector<ull>(1<<18);
        f[1]=vector<ull>(1<<12);
        f[2]=vector<ull>(1<<6);
        f[3]=vector<ull>(1);
    }
    #define LB(x) __builtin_ctzll(x)
    #define HB(x) (63^__builtin_clzll(x))
    #define P (x>>6)
    #define S (x&63)
    #define C (1ull<<S)
    void ins(int x) {
        for(int i=0;i<4;i++,x>>=6) {
            if(f[i][P]&C) return;
            f[i][P]^=C;
        }
    }
    void del(int x) {
        for(int i=0;i<4;i++,x>>=6) {
            if(f[i][P]^=C) return;
        } 
    }
    bool count(int x) {
        return f[0][P]&C;
    }
    int nxt(int x){
        for(int i=0;i<4;i++,x>>=6) {
            if(f[i][P]>>S>1){//注：这里写 f[i][P]>>S+1 是 UB，会爆炸
                x=P<<6|LB(f[i][P]>>S+1<<S+1);
                for(int j=i;~--j;) x=x<<6|LB(f[j][x]);
                return x;
            }
        } return -1;
    }
    int pre(int x){
        for(int i=0;i<4;i++,x>>=6) {
            if(f[i][P]&C-1){
                x=P<<6|HB(f[i][P]&C-1);
                for(int j=i;~--j;) x=x<<6|HB(f[j][x]);
                return x;
            }
        } return -1;
    }
}