01Trie 及其拓展

yzq_yzq · 2024-01-31 20:26:58 · 个人记录

Trie

字典树，空间是 O(\sum len_i c) ， len_i 是字符串长度， c 是字符个数。

插入复杂度就是 O(len) ，删除也是同样。

01Trie

把数的二进制当作一个字符串插入。

空间 O(32n) ，时间 O(32) （插入）

可以通过贪心求最大异或和。

但很容易被忽视的就是他能做普通平衡树。

求第 k 大：从高位往低位选，如果这一位选 1 小于它的数超了，就选 0，否则选 1，然后减去 0 子树的 size，选 1 的子树。

求 rank ：很简单，从高位往低位，如果是 1 就加上 0 子树的 size

空间比较大所以加强版过不去。

代码：

template <int TT>
struct Trie {
    int T[TT * 33][2], num[TT * 33], cnt, root, size, P = 10000000;
    Trie() {
        for (int i = 0; i < TT; i++) T[i][0] = num[i] = T[i][1] = 0;
        cnt = 0;
        cnt = 1, root = 1, size = 0;
    }
    inline void insert(int val) {
        val += P;
        ++size;
        for (int i = 31, rt = root, t; ~i; i--) {
            if (!T[rt][(t = val >> i & 1)])
                T[rt][t] = ++cnt;
            num[rt = T[rt][t]]++;
        }
        return;
    }
    inline void erase(int val) {
        val += P;
        --size;
        for (int i = 31, rt = root, t; ~i; i--) {
            if (!T[rt][(t = val >> i & 1)])
                T[rt][t] = ++cnt;
            num[rt = T[rt][t]]--;
        }
        return;
    }
    inline int rank(int val) {
        int ret = 0;
        val += P;
        for (int i = 31, rt = root, t; ~i; i--) {
            if ((t = val >> i & 1))
                ret += num[T[rt][0]];
            rt = T[rt][t];
        }
        return ret + 1;
    }
    inline int rank_find(int k) {
        int ret = 0;
        for (int i = 31, rt = root, t; ~i; i--) {
            if (k > num[T[rt][0]])
                ret |= 1 << i, k -= num[T[rt][0]], rt = T[rt][1];
            else
                rt = T[rt][0];
        }
        return ret - P;
    }
};

压位 Trie

不会

分层存儿子，一般是压位，取 w=64 （unsigned long long）

然后一个结点的儿子就能用一个 ull 压位存，就可以维护前驱后继，max 和 min。

用位运算乱搞就行，配合 built_clz 和 built_ctz ，但注意复杂度要控制在 O(\log_w V)

不然就白写了，可能跑不过普通01Trie。

空间建议动态开，然后就是这东西是个 set，不支持重复数，只会存一个，删了就一起没，所以也不太实用。

//clz:高位第一个1前0个数
//ctz:低位第一个1后0个数

给个实现

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define drep(i, x, y) for (int i = x; i >= y; --i)
#define ll long long
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define ull unsigned long long
using namespace std;
struct Trie {
    ull * f[5];
    Trie() {
        f[0] = new ull[1 << 24];
        f[1] = new ull[1 << 18];
        f[2] = new ull[1 << 12];
        f[3] = new ull[1 << 6];
        for(int i = 0; i < 4; ++i) memset(f[i], 0, sizeof f[i]);
    }
    inline void ins(int x) {
        for(int i = 0; i < 4; ++i, x >>= 6) {
            if(f[i][x >> 6] & (1ull << (x & 63))) return;
            f[i][x >> 6] |= (1ull << (x & 63));
        }
    }
    inline void del(int x) {
        for(int i = 0; i < 4; ++i, x >>= 6) {
            f[i][x >> 6] ^= (1ull << (x & 63));
            if(f[i][x >> 6] != 0) return;
        }
    }
    inline int nxt(int x) {
        for(int i = 0; i <= 4; ++i, x >>= 6) {
            if(i == 4) return -1;
            if((x & 63) == 63) continue;
            if(f[i][x >> 6] >> ((x & 63) + 1)) {
                ull c = (f[i][x >> 6] >> ((x & 63) + 1)) << ((x & 63) + 1);
                x = ((x >> 6) << 6) |  __builtin_ctzll(c);
                for(int j = i - 1; j >= 0; --j) x = (x << 6) + __builtin_ctzll(f[j][x]);
                return x;
            }
        }
    }
    inline int pre(int x) {
        for(int i = 0; i <= 4; ++i, x >>= 6) {
            if(i == 4) return -1;
            if(f[i][x >> 6] & ((1ull << (x & 63)) - 1)) {
                ull c = ((f[i][x >> 6] & ((1ull << (x & 63)) - 1)));
                x = ((x >> 6) << 6) | (63 - __builtin_clzll(c));
                for(int j = i - 1; j >= 0; --j) x = (x << 6) + (63 - __builtin_clzll(f[j][x]));
                return x;
            }
        }
    }
} t;
int main() {
    t.ins(0);
    while(1) {
        int op;
        cin >> op;
        if(op == 1) {
            int x;
            cin >> x;
            t.ins(x);
        }
        if(op == 2) {
            int x;
            cin >> x;
            t.del(x);
        }
        if(op == 3) {
            int x;
            cin >> x;
            cout << t.pre(x) << endl;
        }
        if(op == 4) {
            int x;
            cin >> x;
            cout << t.nxt(x) << endl;
        }
    }
    return 0;
}

不确定写没写对。

例题的话有 Dpair 自己造的 ---> 链接

不容易考，但是有时候可以配合莫队，因为正常 V = 10 ^ 9 ，\log_w V 是 5，就可以看作大常数 n \sqrt n ，于是就可以做 WC秃子酋长。

虚树 Trie

不会

trick（正片）

支持区间 Sort

例题：

「LibreOJ β Round #2」计算几何瞎暴力

给出序列 A

进行以下几种操作：

1.在 A 末尾添加 x .

2.输出 \sum_{i = l} ^ {r} A_i

3.将 A 中所有数变为 A_i \bigoplus x

4.将 A 排序

trick ：用 Trie 维护排序后的序列。

怎么维护？

考虑一个子问题：维护一个序列，可以整体异或一个数和整体排序，询问区间和。

命 Sum(i) = \sum_{i = 1}^r A_i ，则 ans = Sum(r) - sum(l - 1)

然后设当前所有数异或的值为 tag ， tag_i 是 tag 二进制的第 i 位

那么你会发现，你遍历树的时候把 tag_i 当作 0 ， tag_i \bigoplus 1 当作 1 ，从高位往低位走，你的遍历顺序就是从小到大的。

求和就只需要维护子树中第 i 位为 1 的数的个数就行了。

简要代码：

inline ll qry(int x) {
    if(!x) return 0;
    int p = 1;
    ll res = 0, val = 0;
    drep(i, 30, 0) {
        if(x <= sz[t[p][tag[i]]]) p = t[p][tag[i]], val |= (tag[i] << i);
        else {
            int ls = t[p][tag[i]];
            x -= sz[ls];
            rep(j, 0, 30) {
                int v = sum[ls][j];
                if(tag[j]) v = sz[ls] - v;
                res += (1ll << j) * v;
            }
            p = t[p][tag[i] ^ 1];
            val |= ((tag[i] ^ 1) << i);
        }
    }
    return res + (val ^ Tag) * x;
}

回归原问题，其实就是把这个子问题加强了一下。

我们把序列划分成两部分，第一部分是参与了近一次排序的数，用 Trie 维护，第二部分直接用前缀和维护即可。

每次排序，就把所有第二部分的数加进 Trie。

查询的时候判断查询是只有第一部分，只有第二部分，还是都包含。

有些细节不太好描述，具体看实现：

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define drep(i, x, y) for (int i = x; i >= y; --i)
#define ll long long
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 200020, SQ = 450;
int tot = 1, flg, t[N * 16][2], sum[N * 16][31], p[N][31], sz[N * 16], tag[33];
int now, n, a[N];

inline void insert(int x) {
    int p = 1;
    drep(i, 30, 0) {
        int c = (x >> i) & 1;
        if(!t[p][c]) t[p][c] = ++tot;
        rep(j, 0, 30) {
            if((x >> j) & 1)
                sum[p][j]++;
        }
        ++sz[p];
        p = t[p][c];
    }
    ++sz[p];
    rep(j, 0, 30) {
        if((x >> j) & 1)
            sum[p][j]++;
    }
    // 记得加叶子
}
inline ll qry(int x) {
    if(!x) return 0;
    int p = 1;
    ll res = 0, val = 0;
    drep(i, 30, 0) {
        if(x <= sz[t[p][tag[i]]]) p = t[p][tag[i]], val |= (tag[i] << i);
        else {
            int ls = t[p][tag[i]];
            x -= sz[ls];
            rep(j, 0, 30) {
                int v = sum[ls][j];
                // 为什么不是 tag[j] ?
                // 因为 tag 是存树中的排序时的 flg，而非现在的 flg
                if((flg >> j) & 1) v = sz[ls] - v;
                res += (1ll << j) * v;
            }
            p = t[p][tag[i] ^ 1];
            val |= ((tag[i] ^ 1) << i);
        }
        //搜索顺序是按 tag[i] 为 0， tag[i] ^ 1 为 1
    }
    //加上 (val ^ flg) * x 是因为可能还有一部分数没有加，因为搜完过后可能没有加叶子节点
    return res + (val ^ flg) * x;
}
inline ll Q(int l, int r) {
    ll res = 0;
    rep(i, 0, 30) {
        int v = p[r][i] - p[l - 1][i];
        if((flg >> i) & 1) v = r - l + 1 - v;
        res += (1ll << i) * v;
    }
    //前缀和维护每一位
    return res;
}
inline ll query(int l, int r) {
    if(r <= now) return qry(r) - qry(l - 1);
    if(l <= now) return qry(now) - qry(l - 1) + Q(now + 1, r);
    return Q(l, r);
    // 查询分类讨论
}
int main() {
    IOS;
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) {
        rep(j, 0, 30) {
            p[i][j] = p[i - 1][j] + ((a[i] >> j) & 1);
        }
    }
    int m;
    cin >> m;
    while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
            int x;
            cin >> x;
            a[++n] = x ^ flg;
            // 注意要 ^ flg ，因为计算时会默认都要 ^flg，而这个数并没有参与之前的修改 ,所以要 ^flg ，这样两次的异或就抵消了
            rep(i, 0, 30) p[n][i] = p[n - 1][i] + ((a[n] >> i) & 1);
            continue;
        } 
        if(op == 2) {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << endl;
            continue;
        } 
        if(op == 3) {
            int x;
            cin >> x;
            flg ^= x;
            continue;
        }
        if(op == 4) {
            rep(i, now + 1, n) insert(a[i]);
            now = n;
            rep(i, 0, 30) tag[i] = (flg >> i) & 1;
            //更新排序的 tag
            continue;
        }
    }
    return 0;
}

Ynoi 有个类似的，但又卡空间又复杂很多，之后补。

\large End