主席树

主席树就是可持久化线段树,至于它为什么叫这个名字,不要问我我也不知道

其本质就是对于每次修改,都是新建一个链。我们知道,主席树每次修改访问的节点数都为logn,因此我们每一次修改占用的空间都是logn,而时间复杂度不会变。相比起普通的线段树,主席树仅仅多了一个新建节点的工作,因此貌似没什么好讲的)雾。

那么为什么要这么操作呢?因为对于每次操作,我们发现如果通过建多颗线段树来记录历史状态显然是十分浪费的,因此我们就需要对此进行优化。正如上面所说,线段树每次修改后只有logn个节点是不同的,因此我们只需要在原来的树上面加上logn个节点。

主席树主要的缺点就是容易被卡空间,因为它的空间复杂度为O(nlogn),时间则和线段树相同为O(nlogn)。

说了这么多,主席树是拿来干什么的呢?主席树的主要用处就是那些需要保存修改前的状态的题目,这样就可以对两次修改内的区间进行一些操作。

我们来看一道例题:洛谷P3834【模板】可持久化线段树 1(主席树)

这道题我们可以将序列看为一个不断插入的过程,使用主席树记录下每次修改后的状态,然后就可以通过查询两个树之间数据的差异来得到区间第k大的数。

国际惯例放一份代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, len, cnt, a[200005], b[200005], rt[200005];
struct tree
{
int l;
int r;
int sum;
} tr[200000 * 18];
int query(int x, int y, int l, int r, int k)
{
if (l == r)
return l;
int mid = (l + r) >> 1;
if (tr[tr[x].l].sum - tr[tr[y].l].sum >= k)
return query(tr[x].l, tr[y].l, l, mid, k);
else
return query(tr[x].r, tr[y].r, mid + 1, r, k - (tr[tr[x].l].sum - tr[tr[y].l].sum));
}
void build(int y, int &x, int l, int r, int val)
{
x = ++cnt;
tr[x] = tr[y];
++tr[x].sum;
if (l == r)
return;
int mid = (l + r) >> 1;
if (val <= mid)
build(tr[y].l, tr[x].l, l, mid, val);
else
build(tr[y].r, tr[x].r, mid + 1, r, val);
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
len = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i)
{
a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
build(rt[i - 1], rt[i], 1, len, a[i]);
}
for (int i = 1; i <= m; ++i)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", b[query(rt[r], rt[l - 1], 1, len, k)]);
}
return 0;
}

 

评论

此博客中的热门博文