无旋平衡树01Trie教程

基本原理:将整数分解为二进制数从高到低插入到Trie中,此时整棵树满足二叉查找树性质(注:只有叶子为实际节点,其他节点为虚拟节点,其实不完全满足二叉查找树性质),插入/删除同普通Trie,名次/Kth同普通二叉查找树,前驱 kth(rank(x)-1) 后继 kth(rank(x)+count(x))

优点:常数极小,实测比Splay快2-3倍,易写易调(不压行只有30+行)
缺点:空间占用大 O(nlogV) 不能维护区间操作 V: 值域大小

代码参考:(由于虚拟节点的存在,名次/Kth同普通平衡树略有出入)

namespace trie {
    //支持多个重复元素
    const int MAXNODE = MAXN * 20 /* min{ N * 上取整(log2(V)), 2^上取整(log2(V)) } */;
    int ch[MAXNODE][2], size[MAXNODE], pool = 2;
    inline void insdel(int x, int d = 1) { //d = +a 插入a个数, d = -a 删除a个数
        int i, u = 1; bool v;
        for(i=MAXLOG-1;i>=0;i--) {
            v = (x >> i) & 1;
            if(!ch[u][v]) ch[u][v] = pool++;
            u = ch[u][v];
            size[u] += d;
        }
    }
    inline int rank(int x) {
        int i, u = 1, res = 0; bool v;
        for(i=MAXLOG-1;i>=0;i--) {
            v = (x >> i) & 1;
            if(v) res += size[ch[u][0]];
            u = ch[u][v];
            if(!u) break;
        }
        return res;
    }
    inline int kth(int k) {
        int i, u = 1, res = 0;
        k++; for(i=MAXLOG-1;i>=0;i--) {
            if(size[ch[u][0]] >= k) u = ch[u][0];
            else k -= size[ch[u][0]], u = ch[u][1], res |= (1 << i);
        }
        return res;
    }
}

暂无评论

发表评论

*