主席树

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

其本质就是对于每次修改,都是新建一个链。我们知道,主席树每次修改访问的节点数都为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;
}

 

“主席树”的一个回复

发表评论

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