可持久化数据结构-持久化Trie和持久化线段树

持久化数据结构能解决的问题

高效的查询数据在过去时间点的状态, 优点是不需要复制完整的数据结构, 节省空间

例如$git$支持回滚的操作

条件

在本身数据结构的拓扑结构不会发生变化

持久化数据结构的算法原理

如果暴力的做法, 假设一共$m$个版本, 算法时间复杂度和空间复杂度都是$m\times n$, 效率很低

持久化数据结构核心思想: 只记录每个版本与上一个版本不同的地方

假设是可持久化线段树, 因为每次最多改变的节点数量是$\log n$级别, 那么空间和时间会优化到$n+m\log n$级别, 非常高效

持久化Trie

能解决的问题

查询历史版本的字符串是否存在

算法步骤

假设插入一些字符串cat, rat, cab, fry

红色节点是根节点, 上图是插入两个字符串的情况

当前插入的是cab, 发现已经有$c$节点, 但是并不是插入的是相同的字符串, 需要分裂, 同时发现也需要用到$a$节点, 那么

• 将$c,a$两个节点复制到当前版本
• 再将$a$指向原来的$t$
• 创建新的节点$b$, 将$a$指向$b$

插入最后一个字符fry后的持久化Trie结构

1. 首先需要指针指向第$i-1$个版本, $p$
2. 新的版本开一个新的节点$q$
3. 判断$p$是否是空节点, 如果不是空节点, 将$p$克隆到$q$, tr[q] = tr[p]

小写字母的持久化trie代码实现

#include <bits/stdc++.h>

using namespace std;

// 代表要插入的字符串数量和版本数量
const int N = 1e6 + 10, M = 1e5 + 10;

// idx代表分配的根节点
int root[M], idx;
// tr_idx代表分配的trie树的节点
int tr[N][26], tr_idx;

void insert(string &s) {
   
    // p是上一个版本的根节点
    int p = root[idx];
    root[++idx] = ++tr_idx;
    // q是当前版本的根节点
    int q = tr_idx;

    for (int i = 0; i < s.size(); ++i) {
   
        char c = s[i];

        // 非关键路径上的点指向上一个版本
        for (int k = 0; k < 26; ++k) {
   
            if (c - 'a' != k) tr[q][k] = tr[p][k];
        }

        tr[q][c - 'a'] = ++tr_idx;
        q = tr[q][c - 'a'];
        p = tr[p][c - 'a'];
    }
}

bool find(string &s, int ver) {
   
    int q = root[ver];
    for (int i = 0; i < s.size(); ++i) {
   
        char c = s[i];
        if (tr[q][c - 'a'] == 0) return false;
        q = tr[q][c - 'a'];
    }
    return true;
}


int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    int op;
    while (cin >> op, op) {
   
        string s;
        if (op == 1) {
   
            cin >> s;
            insert(s);
        }
        else {
   
            int ver;
            cin >> s >> ver;
            cout << (find(s, ver) ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

例题

两个操作

• 序列末尾添加一个数很简单, 单点修改, 几乎任何数据结构都能实现
• 在区间$[l,r]$找到一个$p$, 使得$a_p\oplus a_{p+1}\oplus ...\oplus a_n\oplus x$

假设计算出了异或前缀和$s_n=a_1\oplus a_2\oplus a_3\oplus ...\oplus a_n$, 那么答案就是

$$s_n\oplus s_{p-1}\oplus x$$

令$t=s_n\oplus x$, 发现$t$是定值, 目标变成了
$$s_{p-1}\oplus t,(l\le p\le r)$$
最大

设$t$的二进制表示是$t=x_0{x}_1{x}_2...x_k$, 求异或的最大值可以使用贪心的思路, 将当前$t$存储到trie中, 对于当前点$i$, 每次尝试访问$\oplus x_i$节点, 这样当前位结果就是$1$, 结果就会更大

(1)先考虑简单情况, 假设$l=1$, 求的区间是$[1,r]$, 那么可以利用持久化Trie解决, 直接查询第$r$个版本, 计算最大值即可

(2)但是实际情况是需要在$[l,r]$之间计算最大值, 考虑如下情况

对于版本$r$, 假设当前最优贪心路线是走左子树

但是因为有了$l$的限制, 因此问题就变成了对于左子树来说是否至少存在一个点的编号是$\ge l$的, 这个条件等价于下标的最大值是否$\ge l$, 因此可以在trie树的每个节点记录当前子树的编号的最大值, 这样问题就得到了解决

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 6e5 + 10, K = 24;

// n相当于版本根节点的索引
int n, m;
int s[N];
int tr[N * K][2], idx;
int root[N];
int max_id[N * K];

void insert(int p, int q, int i, int k) {
   
    if (k < 0) {
   
        max_id[q] = i;
        return;
    }

    int val = s[i] >> k & 1;
    if (p) tr[q][val ^ 1] = tr[p][val ^ 1];
    tr[q][val] = ++idx;
    insert(tr[p][val], tr[q][val], i, k - 1);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int ql, int qr, int val) {
   
    int u = root[qr];

    for (int i = K - 1; i >= 0; --i) {
   
        int v = val >> i & 1;
        if (max_id[tr[u][v ^ 1]] >= ql) u = tr[u][v ^ 1];
        else u = tr[u][v];
    }

    return val ^ s[max_id[u]];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    max_id[0] = -1;
    root[0] = ++idx;
    insert(0, root[0], 0, K - 1);

    for (int i = 1; i <= n; ++i) {
   
        int val;
        cin >> val;
        s[i] = s[i - 1] ^ val;
        root[i] = ++idx;
        insert(root[i - 1], root[i], i, K - 1);
    }

    char c;
    int l, r, val;
    while (m--) {
   
        cin >> c;
        if (c == 'A') {
   
            cin >> val;
            n++;
            root[n] = ++idx;
            s[n] = s[n - 1] ^ val;
            insert(root[n - 1], root[n], n, K - 1);
        }
        else {
   
            cin >> l >> r >> val;
            int ans = query(l - 1, r - 1, s[n] ^ val);
            cout << ans << '\n';
        }
    }

    return 0;
}

持久化线段树(主席树)

能解决的问题

给定序列, 查询$[l,r]$区间内第$k$大的数字

性质

• 因为持久化线段树有多个版本, 不能用堆的存储方式, 需要动态开点, 也就是需要节点的时候将节点建立
• 因为持久化线段树有多个版本, 普通线段树在执行区间修改的时候需要维护延迟标记, 但是持久化线段树难以维护, 因此持久化线段树一般不支持区间修改(除非标记永久化)

算法步骤

假设修改的是红***域圈住的点, 线段树最多修改$\log n$个点, 右边是复制过来新的点

持久化线段树记录的节点信息

struct Node {
   
    // 左右儿子节点的下标
    int ls, rs;
    // 当前节点区间的数字的个数
    int cnt;
};

模板示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10, M = 1e6 + 10;

int n, m, w[N];
struct Node {
   
   int ls, rs;
   int val;
} tr[N * 4 + N * 20];
int root[N], idx;

int build(int l, int r) {
   
   int u = ++idx;
   tr[u] = {
   0, 0, 0};
   if (l == r) {
   
      tr[u].val = w[l];
      return u;
   }

   int mid = l + r >> 1;
   tr[u].ls = build(l, mid);
   tr[u].rs = build(mid + 1, r);

   return u;
}

int update(int p, int l, int r, int x, int val) {
   
   int u = ++idx;
   tr[u] = tr[p];
   if (l == r) {
   
      tr[u].val = val;
      return u;
   }

   int mid = l + r >> 1;
   if (x <= mid) tr[u].ls = update(tr[p].ls, l, mid, x, val);
   else tr[u].rs = update(tr[p].rs, mid + 1, r, x, val);

   return u;
}

int query(int p, int l, int r, int x) {
   
   if (l == r) return tr[p].val;
   int mid = l + r >> 1;

   if (x <= mid) return query(tr[p].ls, l, mid, x);
   return query(tr[p].rs, mid + 1, r, x);
}

int main() {
   
   ios::sync_with_stdio(false);
   cin.tie(0);

   cin >> n >> m;
   for (int i = 1; i <= n; ++i) cin >> w[i];

   root[0] = build(1, n);

   int v, op, p, c;
   for (int i = 1; i <= m; ++i) {
   
      cin >> v >> op >> p;
      if (op == 1) {
   
         cin >> c;
         root[i] = update(root[v], 1, n, p, c);
      }
      else {
   
         int ans = query(root[v], 1, n, p);
         cout << ans << '\n';
         root[i] = root[v];
      }
   }

   return 0;
}

例题

首先考虑暴力做法, $m$,次询问, 区间大小最坏情况下$n$, 算法时间复杂度$O(m\cdot n\log n)$, 无法通过

一般该问题有两种做法

• 线段树套平衡树, 支持第$k$大数字修改操作, 算法时间复杂度$O(M{\log }^{2}N)$
• 持久化线段树, 算法时间复杂度$O(N\log N)$

具体的算法实现

1. 因为$A_i\le 10^9$, 将所有数据进行离散化, 数据范围变到了$[0,N-1]$
2. 在数值上建立线段树(权值线段树), 维护区间的一共有多少个数字

问题变成了如何在整体上求第$k$小数?

(1) 假设不加限制求$[0,n-1]$的第$k$小数是多少
可以用整数二分实现, 具体的来说

• 假设权值线段树维护区间$[0,n-1]$, 那么假设中点是$mid$
• 求区间$[0,mid]$区间的数字个数假设是$cnt$, 判断$cnt>=k$是否成立
• 如果$cnt>=k$成立, 递归到左边区间
• 否则递归到右边区间

因为只有$\log n$层, 最多访问$\log n$个节点, 算法时间复杂度$O(n\log n)$

(2) 但是要求在$[l,r]$之间求第$k$小数

• 可以使用可持久化线段树, 直接查询第$r$个版本
• 并且因为持久化线段树的结构不会发生变化(线段树节点数量不会发生变化, 新增的点不过是在原基础上修改的点)
• 具体的来说, 假设当前节点存储的是$t$个数字, 新版本节点在原版本节点基础上存储了$t^{\prime }$个数字, 那么变化量就是$t^{\prime }-t$个数字
• 因此对于当前节点的节点数可以用前缀和思想, 节点数是$C_r-C_{l-1}$

代码实现

• 线段树节点空间需要多开$M\log n$个区间, 因此线段树节点数量$4N+M\log N$
• 插入节点的过程中, 遍历$\log n$个节点, 对这$\log n$个节点都要创建新的节点, 最终返回的是构建完的新的根节点, 也就是root[i]
• 查询的时候利用二分算法, 如果当前左子树的差小于等于$k$, 那么结果在左子树, 否则在右子树, 但是注意排名要变成$k-cnt$
• 因为对离散化后建立权值持久化线段树, 设$t$是离散化后的数的个数(也可以表示为离散化后的数值的最大值$+1$), 构建的线段树的范围是$[0,t-1]$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, w[N];
struct Node {
   
    // 左右儿子节点的下标
    int ls, rs;
    // 当前节点区间的数字的个数
    int cnt;
} tr[4 * N + 17 * N];
int root[N], idx;
vector<int> nums;

int find(int x) {
   
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

void pushup(int u) {
   
    tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt;
}

int build(int l, int r) {
   
    int p = ++idx;
    if (l == r) return p;

    int mid = l + r >> 1;
    tr[p].ls = build(l, mid);
    tr[p].rs = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x) {
   
    int u = ++idx;
    tr[u] = tr[p];
    if (l == r) {
   
        tr[u].cnt++;
        return u;
    }

    int mid = l + r >> 1;
    if (x <= mid) tr[u].ls = insert(tr[p].ls, l, mid, x);
    if (x > mid) tr[u].rs = insert(tr[p].rs, mid + 1, r, x);

    pushup(u);
    return u;
}

// 查询区间第k小数
int query(int p, int q, int l, int r, int k) {
   
    if (l == r) return nums[l];

    int mid = l + r >> 1;
    // 当前版本q左边节点数 - 旧p版本左半边节点数
    int cnt = tr[tr[q].ls].cnt - tr[tr[p].ls].cnt;
    if (k <= cnt) return query(tr[p].ls, tr[q].ls, l, mid, k);

    return query(tr[p].rs, tr[q].rs, mid + 1, r, k - cnt);
}


int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        cin >> w[i];
        nums.push_back(w[i]);
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    int t = nums.size();
    root[0] = build(0, t - 1);

    // 构建持久化线段树, 当前版本的根节点在递归完成后返回
    for (int i = 1; i <= n; ++i) {
   
        root[i] = insert(root[i - 1], 0, t - 1, find(w[i]));
    }

    while (m--) {
   
        int l, r, k;
        cin >> l >> r >> k;
        cout << query(root[l - 1], root[r], 0, t - 1, k) << '\n';
    }

    return 0;
}