压位 trie

lgswdn_SA · 2022-08-27 17:58:45 · 个人记录

压位 trie

参考了￥鸽鸽的论文以及有关博客

支持操作：Dynamic Predecessor，即动态维护不可重集的插入，删除，前驱/后继查询。

时间复杂度：单次操作 O(\log_w V)，其中 V 为值域，w 取 64。

压位 trie 本质上是一棵 w 叉 trie，其中每一个节点都像 trie 一样对应一段值域区间。一个节点被点亮了，当且仅当其子树内存在仍在集合内的数字。

我们对于每一个节点记录一个压位的数字 a，其中第 x 位表示它的第 x 个儿子有没有被点亮（下图中根节点也应该是被点亮的，图自论文）。

分析一下空间复杂度。这个压位 trie 动态开点会磨灭其因为有二进制数位所以能够快速进行一些操作的优越性。而在不动态开点的情况下，一个有 V 个叶节点的满 w 叉树的节点数量显然是 O(V) 的。但是由于叶节点上不会记录任何信息（没有儿子），所以叶节点可以直接抛弃。所以实际上空间复杂度是 O(\frac{V}{w}) 的。

分析一下时间复杂度。显而易见的，这个树的深度是 O(\log_w V)，也就是说我们可以用单次操作 O(\log_w V) 的时间解决一些问题。

如何存储一个压位 trie？由于其是一个满 w 叉树，我们有更加简便的存储方法（以更加方便地获取一个节点的位置，这点和 zkw 线段树有些相似）—— 我们对于每一层都开一个数组 A，记录同一层的那些值。具体而言，A_{i,j} 表示高度为 i 的，从左往右的第 j 个节点的儿子情况（即上文提到的 a）。

如何实现插入，删除和前驱后继的查询？

插入

插入 x，即是找到 x 所在的叶节点，然后点亮其到根节点的路径上的节点。我们发现需要点亮的点一定是从叶节点往上的连续的一段，于是为了减小常数，我们可以定位到叶节点后往上爬，爬到已经被点亮的就直接润。
删除

删除 x，即是找到 x 所在的叶节点，然后熄灭其到根节点上所有子树中仅有 x 被点亮的节点，即其的 a 只有一位是 1，然后这一位在操作中被删掉了。同样的，我们熄灭的节点也是叶节点往上爬连续的一段路径，遇到不需要熄灭的节点就直接润。
前驱

查询 x 的前驱，往上爬。对于目前的节点 p 和父节点 q，如果 q 中没有比 p 更靠左的被点亮的节点（即 p 节点是 a_q 的 lowest bit），那么就继续往上跳；否则前驱必然在左侧，我们往那个 lowest bit 的节点跑，找到子树内最大值。
后继

和前驱类似，只不过这次的 lowest bit 变成了 highest bit，最大值变成了最小值。

在代码的具体实现时，有很多技巧方法。设 w=2^g。

存储建树

考虑自行开一个内存池，动态分配空间。高度为 d 的层（其中原叶节点的父亲节点，即舍去没有值的节点后得到的树的叶节点的高度为 0）的节点数为 \lfloor\frac{V+2^{g(d+1)}-1}{2^{g(d+1)}}\rfloor。不断从下往上建，直到节点数成为 0，这就是得到的根节点。
找出边

对于 x，假设目前在高度为 d 的层，我们需要找到它在这一层应该是哪一条边，即 w 进制下的第 d 位。这个可以通过 x 右移 i*g 后按位与上一个 mask=w-1 来解决。
求前驱后继时的贡献，以及最低/最高位

有两个东西：clz 和 ctz，其中 ctz 为最低位（从低往高数），clz 为最高位（从高往低数）。这个可以用 c++ 中的 __builtin_clzll （内置小粉兔）和 __builtin_ctzll 来简单实现。

要注意不能右移 64 ！！！会炸！！！

namespace WTrie {
    #define clz(x) __builtin_clzll(x)
    #define ctz(x) __builtin_ctzll(x)
    #define e 1ull
    const int g=6,mask=63,w=64;
    int d; ull buff[1<<25],*bf=buff,*a[6];
    ull *nowa(int sz) {bf+=sz; return bf-sz;}

    void build(int V) {
        for(d=0;;d++) {
            int c=(V+(e<<(d+1)*g)-1)>>(d+1)*g; a[d]=nowa(c);
            if(c==1) return;
        }
    }
    void ins(int x) {
        rep(i,0,d) {
            int p=x>>i*g&mask, s=x>>(i+1)*g;
            if(a[i][s]&(e<<p)) return; a[i][s]|=(e<<p);
        }
    }
    void del(int x) {
        rep(i,0,d) {
            int p=x>>i*g&mask, s=x>>(i+1)*g;
            a[i][s]&=~(e<<p); if(a[i][s]) return;
        }
    }
    int pre(int x) {
        rep(i,0,d) {
            int p=x>>i*g&mask, s=x>>(i+1)*g; ull v=a[i][s], u=v&((e<<p)-1);
            if(u) {
                int res=(x>>(i+1)*g<<(i+1)*g)+((mask-clz(u))<<i*g);
                per(j,i-1,0) res+=(mask-clz(a[j][res>>(j+1)*g]))<<j*g;
                return res;
            }
        } return 0;
    }
    int suc(int x) {
        rep(i,0,d) {
            int p=x>>i*g&mask, s=x>>(i+1)*g; ull v=a[i][s], u=(v>>p)>>1; //不能用p+1
            if((v>>p)>>1) {
                int res=(x>>(i+1)*g<<(i+1)*g)+((ctz(u)+p+1)<<i*g);
                per(j,i-1,0) res+=ctz(a[j][res>>(j+1)*g])<<j*g;
                return res;
            }
        } return 0;
    }
}

测板子：https://www.luogu.com.cn/problem/U156719，不过该题样例挂了

在这题中 3\times 10^7 次，值域为 [0,2^{32}) 的随机操作，运行了约 2s（包括生成操作所用时间）。

WC2022 秃子酋长

卡常然后搞了个鬼畜块长。

#define abs(x) ((x)>=0?(x):-(x))
int calc(int x,int y,int z,int res=0) {
    if(y) res+=abs(p[x]-p[y]);
    if(z) res+=abs(p[x]-p[z]);
    if(y&&z) res-=abs(p[y]-p[z]);
    return res;
}
void ins(int x) {
    int y=WTrie::pre(x), z=WTrie::suc(x);
    cans+=calc(x,y,z); WTrie::ins(x);
}
void del(int x) {
    int y=WTrie::pre(x), z=WTrie::suc(x);
    cans-=calc(x,y,z); WTrie::del(x);
}

signed main() {
    n=read(), m=read(), bs=n/(sqrt(m)+2)*1.2+10;
    rep(i,1,n) a[i]=read(), p[a[i]]=i, b[i]=i/bs;
    rep(i,1,m) q[i].l=read(), q[i].r=read(), q[i].id=i;
    sort(q+1,q+m+1,cmp);
    WTrie::build(1<<20);
    int l=1,r=0;
    rep(i,1,m) {
        while(l>q[i].l) ins(a[--l]);
        while(r<q[i].r) ins(a[++r]);
        while(l<q[i].l) del(a[l++]);
        while(r>q[i].r) del(a[r--]);
        ans[q[i].id]=cans;
    }
    rep(i,1,m) printf("%lld\n",ans[i]);
    return 0;
}