可持久化线段树/主席树 基础原理和例题

声明：因可持久化线段树的图片不好找，故转载使用JK金坤的图片辅助说明，各位读者有兴趣可以去看JK金坤的求区间第K小的题解，也讲的很清楚。

可持久化线段树，看到名字，就知道一定和线段树相关，在此，对于线段树的原理就不再赘述，读者若不懂可自行百度。可持久化，就是让一个数据结构做到能够访问任何一个历史状态。总体说来，让线段树持久化并不算太复杂。接下来，让我们从一道例题入手。

【OpenJudge1001】Challenge 1
总时间限制: 10000ms
单个测试点时间限制: 1000ms
内存限制: 262144kB

描述 给一个长为N的数列，有M次操作，每次操作是以下两种之一： （1）修改数列中的一个数 （2）求数列中某位置在某次操作后的值

输入 第一行两个正整数N和M。 第二行N个整数表示这个数列。
接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的值修改为y；若该字符为'Q'，则表示一个询问操作，接下来两个整数x和y，表示求x位置在第y次操作后的值。
输出 对每一个询问操作单独输出一行，表示答案。

样例输入
5 3
1 2 3 4 5
Q 1 0
M 1 3
Q 1 2
样例输出
1
3
提示
1<=N<=$10^5$，1<=M<=$10^5$，输入保证合法，且所有整数可用带符号32位整型存储。

这道题很水，操作很简单，单点修改，历史单点查询，甚至连区间都涉及不到。各位读者可能马上想到可以离线操作，先把所有操作读入，在按时间从前往后操作，每次操作后看是否有询问在此时进行，记录答案，最后按询问顺序输出。这样做无疑是能A掉这道简单题的，但如果我们要在线做呢？

1.记录历史版本
在线做的话，各位读者可能会首先想到，对于每次修改，把修改前后的列都存下来，并标记是哪次操作后的数列，询问的时候按时间查询即可。但这时就出现了一个问题：题目中原数列最长有$10^5$个数，$10^5$次询问，如果前$10^5-1$次询问都是更改某个数，最后一次才是询问某位置的数在t时间的值，那我们需要存储$10^5*10^5$个数，肯定会爆空间。
到这里，各位聪明的读者一定又想到了一个方法：每次只记录更改的值，不记录不变的数值，这样可以少消耗大量空间。为了快速实现这一过程，避免麻烦，我们想到了一个数列操作的方便数据结构，线段树。

2.部分修改的线段树
对于每次修改，我们都只会存储修改的值，而对于一颗线段树来说，我们则存储从这个叶子结点到树根的这条链上的节点。
如下图，如果我们要修改第4个数，即修改[4,4]，我们只会新建三个节点：[4,4][3,4][1,4]，并把这些节点的子节点中没有修改的节点指向原来对应的子节点，即[1,4]指向原树中的[1,2]和新建的[3,4]，[3,4]指向原树中的[3,3]和新建的[4,4]。
这样一来，对于每次修改，我们只用新建$log2n$个节点，空间够了。

3.函数式线段树
我们解决了空间的问题，但这个时候，我们又有了一个细节上的问题：新建节点的编号怎么定？肯定不能像以前写普通的堆式线段树一样，左儿子编号是节点编号乘二，右儿子编号是节点编号乘二加一。这里我们只添加一条链，不能那样编号。如果有写过字典树或AC自动机的读者，可以类比得出这里需要函数式建树，即记录一个当前的总节点数cnt，每增加一个节点，这个新节点的编号为cnt+1，随后cnt++。
除此之外，我们可以知道，第t时刻的数列，对应到线段树中就是以第t个树根为树根的那颗线段树，因而我们需要记录每个时刻对应线段树的根，即root[]。

接下来给出代码实现：

#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct node {int ls, rs, val;} tr[2000000]; //每个节点三个值，ls为左儿子编号，rs为右儿子编号，val为该节点权值
int n, m, cnt, now;
int root[MAX_N+5];  //root数组记录每个时刻对应那颗线段树的树根
void build(int v, int s, int t) {
    if (s == t) {
        scanf("%d", &tr[v].val);
        //若已到叶子结点，则读入
        return;
    }
    tr[v].ls = ++cnt;   //新建左儿子，编号为节点总数+1
    tr[v].rs = ++cnt;   //新建右儿子，编号为节点总数+1
    int mid = s+t>>1;
    //递归新建两个子区间
    build(tr[v].ls, s, mid);
    build(tr[v].rs, mid+1, t);
}
void modify(int v, int s, int t, int ori, int pos, int x) {
    //ori为原树上v节点对应的原节点
    tr[v] = tr[ori];    
    //先将ori的各项成员参数赋给v，因为我们会选ori左右儿子中的一个进行修改和新建，它的另外一个儿子会保留
    if (s == t) {
        tr[v].val = x;
        //若已到叶子结点，则修改并返回
        return;
    }
    int mid = s+t>>1;
    if (pos <= mid) {
        //若pos在左区间，我们要修改左儿子，在这里即新建一个左儿子，和建树一样，要++cnt
        tr[v].ls = ++cnt;
        modify(tr[v].ls, s, mid, tr[ori].ls, pos, x);
    } else {
        //原理同上
        tr[v].rs = ++cnt;
        modify(tr[v].rs, mid+1, t, tr[ori].rs, pos, x);
    }
    //注：上面递归modify修改时，传参数要小心，对于ori这项参数，左子节点的原节点是tr[ori].ls，不该直接传ori，右边同理
}
int query(int v, int s, int t, int pos) {
    if (s == t) return tr[v].val;
    int mid = s+t>>1;
    if (pos <= mid) return query(tr[v].ls, s, mid, pos);
    else    return query(tr[v].rs, mid+1, t, pos);
}
int main() {
    scanf("%d%d", &n, &m);
    now = 0, cnt = 0;
    root[now] = ++cnt;  //原树根为1
    build(root[now], 1, n);
    while (m--) {
        char ch;    int a, b;
        cin >> ch >> a >> b;
        if (ch == 'Q') {
            now++;  //时间戳++
            root[now] = root[now-1];    //树根没变，所以用上一个树根
            printf("%d\n", query(root[b], 1, n, a));
            //从root[b]，即b时刻的树根开始query
        }
        if (ch == 'M') {
            now++;  //时间戳++
            root[now] = ++cnt;  //新建一个树根，并从它开始修改
            modify(root[now], 1, n, root[now-1], a, b);
        }
    }
    return 0;
}

各位读者应该看懂了吧，接下来，我们再来做一道简单题练手

【OpenJudge1002】Challenge 2 总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制:
262144kB

描述 给一个空数列，有M次操作，每次操作是以下三种之一： （1）在数列后加一个数 （2）求数列中某位置的值
（3）撤销掉最后进行的若干次操作（1和3）

输入 第一行一个正整数M。
接下来M行，每行开头是一个字符，若该字符为'A'，则表示一个加数操作，接下来一个整数x，表示在数列后加一个整数x；若该字符为'Q'，则表示一个询问操作，接下来一个整数x，表示求x位置的值；若该字符为'U'，则表示一个撤销操作，接下来一个整数x，表示撤销掉最后进行的若干次操作。
输出 对每一个询问操作单独输出一行，表示答案。

样例输入
9
A 1
A 2
A 3
Q 3
U 1
A 4
Q 3
U 2
Q 3
样例输出
3
4
3

提示 1<=M<=10^5，输入保证合法，且所有整数可用带符号32位整型存储。

读者请先自己想想，再继续看。
因为本题和上题差不多，很简单，所以不再赘述，各位读者可直接看代码

代码如下：

#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct node {int ls, rs, val;} tr[2000000+5];
int n, cnt, now;
int num[MAX_N+5], root[MAX_N+5];    //num数组用于存储每个时刻数列的长度，以便知道该从哪里修改
void build(int v, int l, int r) {
    if (l == r) return;
    int mid = l+r>>1;
    tr[v].ls = ++cnt;
    tr[v].rs = ++cnt;
    build(tr[v].ls, l, mid);
    build(tr[v].rs, mid+1, r);
}
void modify(int v, int l, int r, int ori, int pos, int x) {
    tr[v] = tr[ori];
    if (l == r) {
        tr[v].val = x;
        return;
    }
    int mid = l+r>>1;
    if (pos <= mid) {
        tr[v].ls = ++cnt;
        modify(tr[v].ls, l, mid, tr[ori].ls, pos, x);
    } else {
        tr[v].rs = ++cnt;
        modify(tr[v].rs, mid+1, r, tr[ori].rs, pos, x);
    }
}
int query(int v, int l, int r, int pos) {
    if (l == r) return tr[v].val;
    int mid = l+r>>1;
    if (pos <= mid) return query(tr[v].ls, l, mid, pos);
    else    return query(tr[v].rs, mid+1, r, pos);
}
int main() {
    scanf("%d", &n);
    now = 0;
    num[now] = 0;
    root[now] = ++cnt;
    build(root[now], 1, n);
    for (int i = 0; i < n; i++) {
        char ch;    int x;
        cin >> ch >> x;
        if (ch == 'A') {
            now++;
            num[now] = num[now-1]+1;
            root[now] = ++cnt;
            modify(root[now], 1, n, root[now-1], num[now], x);
        }
        if (ch == 'Q') {
            printf("%d\n", query(root[now], 1, n, x));
        }
        if (ch == 'U') {
            now++;
            num[now] = num[now-1-x];
            root[now] = root[now-1-x];
        }
    }
    return 0;
}

上面是最最基础的可持久化线段树，接下来我们来看一个基础的应用：区间第k小

【POJ2104】K-th Number Time Limit: 20000MS Memory Limit: 65536K

Description You are working for Macrohard company in data structures
department. After failing your previous task about key insertion you
were asked to write a new data structure that would be able to return
quickly k-th order statistics in the array segment. That is, given an
array a[1...n] of different integer numbers, your program must answer
a series of questions Q(i, j, k) in the form: "What would be the k-th
number in a[i...j] segment, if this segment was sorted?" For example,
consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2,
5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment,
we get (2, 3, 5, 6), the third number is 5, and therefore the answer
to the question is 5.

Input The first line of the input file contains n --- the size of the
array, and m --- the number of questions to answer (1 <= n <= 100 000,
1 <= m <= 5 000). The second line contains n different integer
numbers not exceeding 109 by their absolute values --- the array for
which the answers should be given. The following m lines contain
question descriptions, each description consists of three numbers: i,
j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the
question Q(i, j, k). Output For each question output the answer to it
--- the k-th number in sorted a[i...j] segment.

Sample Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output
5
6
3

题目大意：给出一个长度为n的序列，针对每次询问，读入a，b，k，求第a个数到第b个数中第k小的数

同样，请各位读者先自行思考，再继续阅读

题解：
1.值域线段树
这道题既然和线段树有关系，肯定先得把这个数列存到线段树里。但我们注意到，我们需要求的是第k小，所以我们不能用普通线段树，而应该是能体现出数与数之间大小关系的线段树，于是我们不难想到值域线段树。节点v的范围是[l,r]，则存储数列在[l,r]范围内的数的个数。找第k小的时候，对于节点v，左右儿子范围分别是[l,mid]和[mid+1,r]，若v.ls.size<=k，则第k小在[l,mid]范围内，所以递归询问左子节点，右边同理，只是询问的是右子节点中的第k-v.ls.size小，注意不再是第k小。

2.离散化
想到了值域线段树，则要注意值域的问题，我们看到题目中值域为int32，直接存肯定爆空间，所以我们需要离散化，即给每个数排序后用序号代替每个数。这样大小关系没有变化，而值域变成1e5了
离散化代码如下：

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)    scanf("%d", &pre[i].val), pre[i].id = i;
sort(pre+1, pre+n+1, cmp);
tot = 0;
for (int i = 1; i <= n; i++) {
    if (pre[i].val != pre[i-1].val) {
        hash[++tot] = pre[i].val;   //hash[p]存储序号p代替的是哪个数
    }
    num[pre[i].id] = tot;   //num[p]存储原来的第p个数被代替为什么数
}

3.前缀和思想

现在我们的难题是：如何把全局第k小变为区间第k小。
这里，我们需要用到前缀和的思想。我们分别存储第1-i个数中范围在[l,r]的数的个数和第1-j个数中范围在[l,r]的数的个数，这样我们若需要第i+1到第j个数中[l,r]的个数，就只用sum[j][l,r]-sum[i][l,r]即可。所以，我们存n颗线段树，第p颗存储第1-p个数中的值域情况。
例如：对于序列7，2，3，5，1，4，3，第4颗树的[2,4]节点存储都是从第一个数到第四个数中值在[2,4]中的数的个数。7，2，3，5中在[2,4]的数为2和3，故此节点的值为2。

4.可持久化线段树
有了以上思路，剩下的问题就是如何把这n颗线段树存进去。直接存一定会爆空间，而注意到每次加一个数后，不是所有节点都发生了改变，因而我们只需要存储有改动的节点，可以使用可持久化线段树。和上面的题一样，我们把新建的节点指回原来的子节点，可以参照前面的说明。

AC代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 100000
using namespace std;
struct node {int ls, rs, val;} tr[MAX_N*20+5];
struct p {int val, id;} pre[MAX_N+5];
bool cmp(const p &a, const p &b) {return a.val < b.val;}
int n, m;
int num[MAX_N+5], hash[MAX_N+5], tot;
int cnt, root[MAX_N+5];
void updata(int v) {tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;}
void build(int v, int s, int t) {
    if (s == t) return;
    tr[v].ls = ++cnt;
    tr[v].rs = ++cnt;
    int mid = s+t>>1;
    build(tr[v].ls, s, mid);
    build(tr[v].rs, mid+1, t);
}
void modify(int v, int s, int t, int ori, int pos, int x) {
    tr[v] = tr[ori];
    if (s == t) {
        tr[v].val += x;
        return;
    }
    int mid = s+t>>1;
    if (pos <= mid) {
        tr[v].ls = ++cnt;
        modify(tr[v].ls, s, mid, tr[ori].ls, pos, x);
    } else{
        tr[v].rs = ++cnt;
        modify(tr[v].rs, mid+1, t, tr[ori].rs, pos, x);
    }
    updata(v);
}
int query(int v1, int v2, int s, int t, int k) {
    if (s == t) return s;
    int mid = s+t>>1, tmp = tr[tr[v2].ls].val-tr[tr[v1].ls].val;
    if (tmp >= k)   return query(tr[v1].ls, tr[v2].ls, s, mid, k);
    else    return query(tr[v1].rs, tr[v2].rs, mid+1, t, k-tmp);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)    scanf("%d", &pre[i].val), pre[i].id = i;
    sort(pre+1, pre+n+1, cmp);
    for (int i = 1; i <= n; i++) {
        if (pre[i].val != pre[i-1].val) {
            hash[++tot] = pre[i].val;
        }
        num[pre[i].id] = tot;
    }
    root[0] = ++cnt;
    build(root[0], 1, n);
    for (int i = 1; i <= n; i++) {
        root[i] = ++cnt;
        modify(root[i], 1, n, root[i-1], num[i], 1);
    }
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", hash[query(root[l-1], root[r], 1, n, k)]);
    }
    return 0;
}

注：本题是可持久化线段树的必写题，想学可持久化线段树的读者一定要写这道题，一定！！！

上面的三道题都是最为简单基础的可持久化

线段树题目，可持久化线段树是可以区间修改的，但是为避免新建过多节点，不能downtag，需要标记永久化，询问的时候一路累加下去就行了，情况可能稍微多一些，有意的读者请去做一道叫To The Moon的题。