本文主要是介绍可持久化数据结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

可持久化数据结构

1. 可持久化数据结构原理

原理

• 可持久化：将数据结构的所有历史版本记录下来，称为可持久化。
• 不是所有的数据结构都是可以持久化的，可持久化的数据结构要求其结构稳定，比如堆（是一颗满二叉树，结构稳定）、树状数组、trie（字典树）、线段树等。平衡树就不可以进行持久化操作，因为其存在左旋、右旋的操作。
• 存下来所有的历史版本有两种方式，一种是每改动一次则全部备份下来；另一种是增量备份。第一种方式时空复杂度都比较高，不使用这种方式，我们这里只讲解增量备份的方式（类似于git）。
• 增量备份的核心思想是：只记录每个版本与前一个版本不同的部分。
• 这里讲解关于trie的可持久化和线段树的可持久化（又被称为主席树）。

trie的可持久化

• 对于trie来说，每次我们只会记录不同的部分，比较节省空间。

• 凡是有变化的节点都要裂开，因为每次跟节点都会变化，因此每插入一个字符串，根节点一定会变化。每次都会开辟一个新的路径，如果这个路径上点原来都存在，则将原来的点的所有信息都克隆过来。
• 接着，我们总结一下插入操作是如何进行的：

p = root[i - 1];  // p表示上一个版本的根节点，递归过程中的根节点（即可能是中间的某个点）
q = root[i] = ++idx;  // q表示当前版本的根节点，也是递归过程中的根节点
if (p) {  // 如果p非空才需要操作，否则当前插入的是第一个字符串
    tr[q] = tr[p];  // 将上一个版本的各节点克隆到这个版本上
}
// 假设当前版本的指针指向字符si，则需要将si所在的节点更新
tr[q][si] = ++idx;  // 为si开辟一个新的点
p = tr[p][si], q = tr[q][si];  // 指针下移
// 直到将当前的单词遍历完成为止

线段树的可持久化

• 线段树的可持久化又被称为主席树。

• 由于存在多个版本，因此线段树的存储方式不能使用堆的方式进行存储了，而是采用指针的方式存储，这里使用结构体：

struct Node {
    int l, r;  // 不是左右边界，而是当前节点的左右儿子的下标
    // 一些其他信息
}

• 另外这种用指针的方式存储线段树，我们就不需要存储左右边界了，直接在递归的过程中将左右边界传递下去即可

2. AcWing上的可持久化数据结构题目

AcWing 256. 最大异或和

问题描述

• 问题链接：AcWing 256. 最大异或和

  

分析

• 我们定义前缀和 S i S_i Si​，表示前i个数的前缀和，第一个数据存储在 a 1 a_1 a1​中，即（ ⨁ \bigoplus ⨁表示异或）：

S 0 = 0 S 1 = a 1 S 2 = a 1 ⨁ a 2 . . . S i = a 1 ⨁ a 2 ⨁ a 3 . . . . . . ⨁ a i S_0 = 0 \\ S_1 = a_1 \\ S_2 = a_1 \bigoplus a_2 \\ ... \\ S_i = a_1 \bigoplus a_2 \bigoplus a_3 ......\bigoplus a_i S0​=0S1​=a1​S2​=a1​⨁a2​...Si​=a1​⨁a2​⨁a3​......⨁ai​

• 这样定义之后，我们需要求解的内容就可以变为：

a p ⨁ . . . . . . ⨁ a n ⨁ x = S p − 1 ⨁ S N ⨁ x a_p \bigoplus ......\bigoplus a_n \bigoplus x = S_{p-1} \bigoplus S_N \bigoplus x ap​⨁......⨁an​⨁x=Sp−1​⨁SN​⨁x

• 上面的式子中我们可以将 S N ⨁ x S_N \bigoplus x SN​⨁x看成常数，记为C，则相当于让我们在区间 [ L , R ] [L, R] [L,R]中找到一个p，使得 S p − 1 ⨁ C S_{p-1} \bigoplus C Sp−1​⨁C的值最大。

• 类似于AcWing 143. 最大异或对，关于这题的讲解可以参考：网址。我们可以将每个数据 a i a_i ai​看成一个二进制的字符串，因为 0 ≤ a [ i ] ≤ 1 0 7 0 \le a[i] \le 10^7 0≤a[i]≤107，又 2 23 ≤ a [ i ] ≤ 2 24 2^{23} \le a[i] \le 2^{24} 223≤a[i]≤224，因此我们需要将每个数据对应到一个长度为24为的01二进制串上。

• 我们可以先考虑一个简单的情况，假设让我们从 [ 1 , R ] [1, R] [1,R]中找到一个这样的p的话，问题就十分类似于AcWing 143. 最大异或对，不同点在于本题中的a数组是不断变化的，因此我们要记录下来所有历史版本的trie树，root[R]中存储的就是插入a[1~R]形成的trie树。

• 如果区间左边的限制也加上，则问题就变成了让我们在区间 [ L , R ] [L, R] [L,R]中找到一个p，使得 S p − 1 ⨁ C S_{p-1} \bigoplus C Sp−1​⨁C的值最大，我们可以这样处理：在trie树中的每个节点中多记录一个信息max_id，表示以当前节点为根的子树所代表的数据中最晚插入的那个数据插入的时间t（即第几个插入的），如果 t ≥ L t \ge L t≥L，则说明这棵子树在 [ L , R ] [L, R] [L,R]这个区间中存在。

• 对于上面提到的某个C，数据A可以看成一个24的二进制字符串，从左到右遍历这个字符串，假设当前考察的是字符t，则在trie树中我们应该走到1^t的分支上（如果存在的话，即对于区间 [ L , R ] [L, R] [L,R]，如果该分支对应的max_id ≥ \ge ≥L，则说明存在），这样异或值才能最大（贪心思想）。

代码

• C++

#include <iostream>

using namespace std;

const int N = 600010, M = N * 25;

int n, m;  // 序列初始长度、操作个数
int s[N];  // 原序列的异或前缀和
int tr[M][2];  // trie中的节点
int max_id[M];  // 以当前节点为根的子树所代表的数据中最晚插入的那个数据插入的时间t(即第几个插入的)
int root[N], idx;  // 记录每个版本，从1开始

// i: 前缀和下标, 表示插入Si
// k: 当前处理到Si的第几位, 从23为开始处理到第0位
// p: 上一个版本的根节点
// q: 当前版本的根节点, 是p的复制, 差别在于新加了一条链
void insert(int i, int k, int p, int q) {
    
    if (k < 0) {  // 说明我们处理完了最后一位(第0位), 此时q就是叶节点的编号
        max_id[q] = i;
        return;
    }
    int v = s[i] >> k & 1;
    // 所有需要修改的节点，不要去修改它，而是拷贝一个新的，然后修改这个新点。
    if (p) tr[q][v ^ 1] = tr[p][v ^ 1];  // 如果上一个版本存在，直接复制过来
    tr[q][v] = ++idx;  // 当前这个二进制位需要开辟一个新的节点
    insert(i, k - 1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);  // 左右儿子取大
}

// 从root开始查询, 需要被异或的数据是C, 区间左端点是L
int query(int root, int C, int L) {
    
    int p = root;
    for (int i = 23; i >= 0; i--) {
        int v = C >> i & 1;
        if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];  // 找不到更好的了，只能将就一下
    }
    return C ^ s[max_id[p]];  // 这个叶子节点只有它自己，因此max_id就是Si的下标i
}

int main() {
    
    scanf("%d%d", &n, &m);
    
    // 这里max_id[0]中的0表示空节点，空节点不包含任何点，
    // 所以它的max_id需要设置成比所有的id都小的数，所以设置成任何负数均可。
    max_id[0] = -1;
    
    root[0] = ++idx;  // 第0个版本在trie中的根节点编号为1
    insert(0, 23, 0, root[0]);  // 在第0个版本中插入S0, 不存在上一个版本
    
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
        root[i] = ++idx;  // 第i个版本
        insert(i, 23, root[i - 1], root[i]);
    }
    
    char op[2];
    int l, r, x;
    for (int i = 1; i <= m; i++) {
        scanf("%s", op);
        if (*op == 'A') {
            scanf("%d", &x);
            n++;
            s[n] = s[n - 1] ^ x;
            root[n] = ++idx;
            insert(n, 23, root[n - 1], root[n]);
        } else {
            scanf("%d%d%d", &l, &r, &x);
            // p在[L, R]之间，p-1在[L-1, R-1]之间
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }
    
    return 0;
}

AcWing 255. 第K小数

问题描述

• 问题链接：AcWing 255. 第K小数

  

分析

• 这是一个超级经典的题目。这是一个静态问题（原数组在操作的过程中不会发生变化）。可以使用以下方法求解：

  （1）归并树，时间复杂度： O ( n × l o g 3 ( n ) ) O(n \times log^3(n)) O(n×log3(n))；

  （2）划分树，时间复杂度： O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))，空间复杂度： O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))；只能解决这一个问题。不是支持区间第k小数的修改。

  （3）树套树，时间复杂度： O ( n × l o g 2 ( n ) ) O(n \times log^2(n)) O(n×log2(n))，空间复杂度： O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))；这里使用线段树套平衡树，线段树中的每个节点是一个平衡树，平衡树中维护的是一个区间的有序序列。该数据结构的好处是支持区间第k小数的修改。

  （4）可持久化线段树（主席树），时间复杂度： O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))，空间复杂度： O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))； 不是支持区间第k小数的修改。

• 本题选择（4）的方法解决。步骤如下：

  （1）保序离散化；

  （2）在离散化后的数值上建立线段树，维护每个区间中一共有多少个数（区间右边代表的数大于区间左边的）；

• 求所有数据的第k小数：

• 假设输入数据存储在数组a中，a[1]存储第一个数据，现在求a[L~R]之间的第k小数，应该怎么处理呢？刚开始root[0]表示没有插入任何数据的线段树，即第0个版本，插入第k个数后的线段树的根节点存储在root[i]中，即第i个版本；

• 求a[L~R]之间的第k小数，我们可以找到第R个版本的线段树根节点root[R]，如果此时在root[R]中查找第k小的数，查找的结果是前R个数中第k小的数。

• 我们需要考虑左边界L，对于每个版本的线段树，结构都是完全一样的，只不过存储的信息不同；类似于前缀和的思想，我们考虑root[L-1]，如果该版本的某个区间[left, right]中元素个数为cnt2个，root[R]对应区间[left, right]中元素个数为cnt1个，则cnt1-cnt2表示的就是第L个数到第R个数中在区间[left, right]中出现的数的次数。

• 最后考虑线段树应该开多大的空间，本题中最多有 N = 1 0 5 N=10^5 N=105个数据，每次插入一个数据就会记录一个版本的信息，会增加一条长度为 ⌈ N ⌉ = 17 \lceil N \rceil=17 ⌈N⌉=17个路径，因此需要的空间大小是 N × 4 + N × 17 N \times 4 + N \times 17 N×4+N×17。

代码

• C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;  // 序列长度、询问个数
int a[N];  // 序列
vector<int> nums;  // 保序离散化数组

struct Node {
    int l, r;  // 当前节点的左右儿子的下标
    int cnt;  // 数据范围在[nums[l], nums[r]]的数据的个数
} tr[N * 4 + N * 17];

int root[N], idx;

// 返回数据x离散化后对应的下标
int find(int x) {
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

// l: 区间左端点, r: 区间右端点
// 返回区间为[l, r]的线段树的根节点
int build(int l, int r) {
    
    int p = ++idx;  // 为当前节点分配节点
    
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    
    return p;
}

// p: 上一个版本的线段树的根节点
// l、r: 线段树某个节点对应区间左端点和右端点
// x: 单点修改线段树中第x个数
// 返回新版本线段树的根节点
int insert(int p, int l, int r, int x) {
    
    int q = ++idx;
    
    tr[q] = tr[p];
    if (l == r) {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    
    return q;
}

// 返回版本(p, q]之间第k小的版本
// 当前遍历到的线段树对应的区间为[l, r]
int query(int p, int q, int l, int r, int k) {
    
    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;  // 左孩子数据个数
    int mid = l + r >> 1;
    if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
    else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

int main() {
    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }
    
    // 保序离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    // 没有插入任何数据对应版本0
    root[0] = build(0, nums.size() - 1);
    
    // 建立各个版本的线段树
    for (int i = 1; i <= n; i++) 
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
    
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)]);
    }
    
    return 0;
}

这篇关于可持久化数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！