数据结构Part 4

说是字符串的，其实单独用一般不会拿来维护字符串，用于字符串的大多是 ACAM。

0.结构

顾名思义，字典树肯定是一棵树。除根结点外每个结点存储的是一个字符（或者在边上存，点上不存），从根结点到任意一点的路径就是一个字符串。

大概长这样：

From oi-wiki.org

一般会对每个结点记录是否是一个字符串的结尾。

1.应用

检索字符串

我们从根结点一路往下走，如果没有需要的下一个字符，就返回没找到。如果找到了最后，就返回是否是结尾。

01-Trie

就是字符集只有 $0,1$ 的字典树，可以维护和异或有关的信息。

Eg. 最长异或路径↗：维护异或极值

我们可以把路径 $(u,v)$ 的查询拆成 $(root,u) \oplus (root,v)$ ，同时记录异或前缀和。

先把所有异或前缀和插入到字典树中，查询 $x$ 的某一位时，采取贪心的策略，优先选相反的结点，然后向下递归。

维护异或和

插入 & 删除

一般是从低位向高位维护。

维护异或和，我们需要知道的是每一位上的奇偶性，为此，我们维护以下几个值：

$w$ 表示到父亲这条边的权值（的奇偶性）
$val$ 表示子树异或和。

我们可以采用 DS 的一贯手法：pushup。

具体如下：我们将 $w$ 更新为两儿子的 $w$ 的和， $val \gets 2val _ {0} \oplus (2val _ {1} \operatorname{or} (w _ {1} \operatorname{and} 1))$ 。

写成代码是这样的：

1
#define son(rt,v) tree[rt].ch[v]
2
inline void pushup(int rt)
3
{
4
    tree[rt].w = tree[rt].val = 0;
5
    if(son(rt,0))
6
    {
7
        tree[rt].w += tree[son(rt,0)].w;
8
        tree[rt].val ^= (tree[son(rt,0)].val << 1);
9
    }
10
    if(son(rt,1))
11
    {
12
        tree[rt].w += tree[son(rt,1)].w;
13
        tree[rt].val ^= (tree[son(rt,1)].val << 1) & (tree[son(rt,1)].w & 1)
14
    }
15
}

按插入值的每一位向下走，走到最后让 $w$ 自增，回溯的时候 pushup 上来，删除就让 $w$ 自减。注意限制 Trie 的高度。

1
inline void insert(int &rt,int x,int dep)
2
{
3
    if(!rt)
4
        rt = newNode();
5
    if(dep > MXDP)
6
    {
7
        ++tree[rt].w;
8
        return ;
9
    }
10
    insert(son(rt,x & 1),x >> 1,dep + 1);
11
    pushup(rt);
12
}
13
inline void remove(int rt,int x,int dep)
14
{
15
    if(dep > MXDP)
16
    {
17
        --tree[rt].w;
18
        return ;
19
    }
20
    remove(son(rt,x & 1),x >> 1,dep + 1);
21
    pushup(rt);
22
}

全局加一

我们思考二进制下的加一过程：

我们找到最低的 $0$ ，然后把它变成 $1$ ，再将后面的 $1$ 全部变成 $0$ 。

放到 Trie 上，就是交换两儿子，顺着交换后的 $0$ 向下递归。

1
inline void add(int rt)
2
{
3
    swap(son(rt,0),son(rt,1));
4
    if(son(rt,0))
5
        add(son(rt,0));
6
    pushup(rt);
7
}

进阶操作

我们可以在把 $w$ 看作出现次数，这样，我们就可以做一些更神奇的操作。

Trie 合并

类似线段树合并，传入两个结点 $L,R$ ，若有至少一个为 $0$ 则返回另一个。

否则，合并两个结点的信息，随后向下递归。

1
inline int merge(int L,int R)
2
{
3
    if(!L || !R)
4
        return L | R;
5
    tree[L].w += tree[R].w;
6
    tree[L].val ^= tree[R].val;
7
    son(L,0) = merge(son(L,0),son(R,0));
8
    son(L,1) = merge(son(L,1),son(R,1));
9
    return L;
10
}

可持久化 Trie

类似主席树，我们每次记录修改的一条链，然后更新根结点。

下面是可以支持查询区间异或最大值的可持久化 Trie。

1
struct Buer
2
{
3
    int val,ch[2];
4
}tree[MAXN * 50];
5
#define son(rt,v) tree[(rt)].ch[(v)]
6
int root[MAXN],cnt;
7
inline void insert(int rt,int o,int val)
8
{
9
    for(int i = U;i >= 0;--i)
10
    {
11
        tree[rt].val = tree[o].val + 1;
12
        if(val & (1 << i))
13
        {
14
            if(!son(rt,1))
15
                son(rt,1) = ++cnt;
16
            son(rt,0) = son(o,0);
17
            rt = son(rt,1),o = son(o,1);
18
        }
19
        else
20
        {
21
            if(!son(rt,0))
22
                son(rt,0) = ++cnt;
23
            son(rt,1) = son(o,1);
24
            rt = son(rt,0),o = son(o,0);
25
        }
26
    }
27
    tree[rt].val = tree[o].val + 1;
28
}
29
// root[i] = ++cnt,insert(root[i],root[i - 1],val);
30
inline int query(int u,int v,int val)
31
{
32
    int res = 0;
33
    for(int i = U;i >= 0;--i)
34
    {
35
        bool t = (val & (1 << i));
36
        if(tree[son(v,!t)].val - tree[son(u,!t)].val)
37
        {
38
            res += (1 << i);
39
            u = son(u,!t),v = son(v,!t);
40
        }
41
        else
42
            u = son(u,t),v = son(v,t);
43
    }
44
    return res;
45
}

结尾

用在 DS 方面的就差不多了，放在字符串里面，还可以拿来跑 ACAM，或者构建后缀字典树解决其他问题。

Thanks for reading!

数据结构Part 4

2025 2月 26 周三

962 字 · 6 分钟

算法学习笔记 OI 数据结构字符串