题解 P3919 【【模板】可持久化数组（可持久化线段树/平衡树）】

· · 题解

luogu3919 【模板】可持久化数组

ps.

鉴于要加深一下可持久化的理解（以及帮助他人更好的理解

再来写一篇题解吧QAQ.

题意：

标题即题意（雾

好了简单说一下吧。

你需要维护这样的一个长度为N的数组，支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值

  2. 访问某个历史版本上的某一位置的值

做法：

首先我们撇开区间第k小，再来理解一下可持久化线段树的意思。

通俗理解：很多个线段树按照一定的顺序建立，每个线段树i都和之前的某个有一定联系，需要拷贝一些之前的信息。

比如一个简单的例子：

维护一个数据结构，支持：

  1. 单点加
  2. 询问区间和
  3. 回到之前某个历史状态

其中第三点就是经典的可持久化应用。

解决这一类问题，简单的想法就是每个状态建立一棵线段树，拷贝之前一棵树的信息，并修改相关信息。

但是发现这样空间不够，于是我们考虑舍弃冗余状态，每次只拷贝需要修改的点，这样就能保证每次只新建log级别的点。

然后考虑这个题，发现是上面这个例子的弱化版（大雾

只要把线段树的操作改成单点修改+单点查询即可。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;

inline ll read() {
    char ch = getchar(); ll x = 0; int op = 1;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') op = -1;
    for(; isdigit(ch); ch = getchar()) x = x*10+ch-'0';
    return x*op;
}
inline void write(ll a) {
    if(a < 0) putchar('-'), a = -a;
    if(a >= 10) write(a/10); putchar('0'+a%10);
}

const int N = 1000010, M = 20000010;
int n, m, tot;
int a[N], rt[N], ls[M], rs[M], v[M];

inline void build(int &nk, int l, int r) {
    nk = ++ tot;
    if(l == r) { v[nk] = a[l]; return; }
    int mid = l+r>>1;
    build(ls[nk], l, mid); build(rs[nk], mid+1, r);
}
inline void update(int k, int &nk, int l, int r, int x, int y) {
    nk = ++ tot; ls[nk] = ls[k]; rs[nk] = rs[k]; v[nk] = v[k];
    if(l == r) { v[nk] = y; return; }
    int mid = l+r>>1;
    if(x <= mid) update(ls[k], ls[nk], l, mid, x, y);
    else update(rs[k], rs[nk], mid+1, r, x, y);
}
inline int query(int nk, int l, int r, int x) {
    if(l == r) return v[nk];
    int mid = l+r>>1;
    if(x <= mid) return query(ls[nk], l, mid, x);
    else return query(rs[nk], mid+1, r, x);
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    build(rt[0], 1, n);
    for(int i = 1; i <= m; i ++) {
        int t = read(), opt = read(), x = read(), y;
        rt[i] = rt[t];
        if(opt == 1) {
            y = read(); update(rt[i], rt[i], 1, n, x, y);
        } else write(query(rt[t], 1, n, x)), puts("");
    } return 0;
}

拓展理解

别急，还没结束。。。

我们再来理解一下区间第k小的主席树操作吧。

仍然是可持久化线段树，但是和上面两种例子都是不太相似的。

主席树求区间第k小，我们需要建立的是权值线段树，于是需要先离散化。

在原序列上建立主席树，每一棵权值线段树i，拷贝第i-1棵线段树的信息，并在上面修改（a_i的权值节点上+1）。

这样我们得到的是一个类似前缀和的主席树。

于是我们可以通过sum_r-sum_{l-1}快速地得到某个节点所代表的权值范围，在区间[l,r]中出现的次数，从而来完成查询操作。

所以，虽说都是可持久化线段树，还是有比较大的区别的。

特别注意不要把可持久化线段树理解为就等于权值线段树~~~

_the end_

by bestFy 2018.1