可持久化线段树 —— ylxmf2005的OI教程

题目

前置芝士:

  1. 线段树
  2. 离散化
  3. 会自己模拟。

给你两个操作:

  1. 对 $k$ 步前的线段树进行区间修改
  2. 查询第 $k$ 小值。

最直观的想法是建立 $n$ 棵线段树,每次修改先新建一棵线段树,然后将历史版本复制再进行修改。复杂度:$O(TLE+MLE)$。

可持久化线段树

可持久化线段树,与主席树大致相同。用于解决对历史版本修改查询的问题。它的最大特点是:可以访问历史版本,核心思想是:对于修改操作,在原来的线段树的基础上,对于修改的节点,不改动原来节点的信息,而是新建一个节点,再把原来节点的信息复制,最后进行修改

我们如何查询和修改历史版本呢?每次线段树的修改查询都是从 根节点 开始的,所以每次修改操作会建立一个新的根节点。所以只需记录每一次修改对应的新根节点编号,查询时从对应根节点开始查询就可了。我们举个栗子(红色是历史版本号):

《可持久化线段树 —— ylxmf2005的OI教程》

比如我们要修改 $[1,2]$ 的值,我们从 $[1,5]$ 出发,新建一个点,复制后走到了 $[1,3]$,然后复制 $[1,3]$ 走到 $[1, 2]$,然后复制 $[1,2]$修改值。最后长成这样(图丑请见谅):

《可持久化线段树 —— ylxmf2005的OI教程》

可以发现,这种做法是很节省空间和时间的。

刚才的题目是带修改的,是动态区间第 $k$ 小,我这里只讲没有修改的静态区间第 $k$ 小。我们先不考虑查询的区间 $[l,r]$,只考虑区间 $[1,r]$。我们用线段树维护每个区间数字出现的次数,数据范围很大,首先离散化

我们可以用一个$root_i$记录线段树的根节点(根节点是一定是不同的)。然后我们就可以通过 $root_i$ 来询问所有线段树。新的问题出现了,那如何解决区间问题呢,我们能求 $[1,i]$ 的第 $k$ 小,但是如何求 $[l,r]$ 的第$k$ 小呢。

$[1,l]$ 线段树是由插入 $a_1$到 $a_l$ 的影响构成的。

$[1,r]$线段树是由插入 $a[1]$ 到 $a[r]$ 的影响构成的。

$[l,r]$ 线段树是由插入 $a_l$ 到 $a_r$ 的影响构成的就同等于 $a_l$ 到 $a_r$ 的影响减去 $a1$ 到 $a{l-1}$ 的影响。所以 $[l,r]$ 线段树 $=[1,r]$ 线段树 $=[1,l-1]$ 线段树。

发现是不是很像前缀和呢? 那么只要 在 $[l,r]$ 线段树的每一个节点上减去 $l – 1$ 线段树上的相同位置的节点的值 就好了。在代码中,我们不是在查询的时间建立新的节点,而是在建树的时候,把每个区间的树都建立起来。

注意事项:

  1. 使用取地址符。
  2. 先建点,后if(l==r) return
  3. 空间要开到$(n+Qlogn)^2$。

模板

洛谷 P3834 可持久化线段树(主席树)

静态区间第 $k$ 小。

#include <bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define re register
#define F first
#define S second
#define mp make_pair
#define lson (p << 1)
#define rson (p << 1 | 1)
typedef long long ll;
typedef pair<int, int> P;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
inline int read() {
    int X = 0,w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48),ch = getchar();
    return w ? -X : X;
}
inline void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
int tot; 
int a[N], b[N], root[N];
struct SegTree {
    int l, r, sum ;
} t[N * 32];
int build(int l, int r) {
    int p = ++tot, mid = (l + r) >> 1;
    if (l != r) t[p].l = build(l, mid), t[p].r = build(mid + 1, r);
    return p;
}
int update(int pre, int l, int r, int x) {
    int p = ++tot;
    t[p].sum = t[pre].sum + 1; 
    t[p].l = t[pre].l; t[p].r = t[pre].r; 
    if (l != r) {
        int mid = (l + r) >> 1;
        if (x <= mid) t[p].l = update(t[pre].l, l, mid, x);
        else t[p].r = update(t[pre].r, mid + 1, r, x);
    }
    return p;
}
int query(int L, int R, int l, int r, int x) {
    if (l == r) return l;
    int tmp = t[t[R].l].sum - t[t[L].l].sum;
    int mid = (l + r) >> 1;
    if (x <= tmp) return query(t[L].l, t[R].l, l, mid, x);
    else return query(t[L].r, t[R].r, mid + 1, r, x - tmp);
}
int main() {
    int n = read(), q = read();
    for (int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    root[0] = build(1, m);
    for (int i = 1; i <= n; i++)
        root[i] = update(root[i - 1], 1, m, lower_bound(b + 1, b + m + 1, a[i]) - b);
    while (q--) {
        int l = read(), r = read(), k = read();
        write(b[query(root[l - 1], root[r], 1, m, k)]), puts("");
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据