【可持久化数据结构初步】

先来一波可持久化线段树,又名主席树。在可持久化数据结构中,能够支持查询历史版本的数据。是对原数据结构的进一步加深与理解,代码和原理也只能算是锦上添花。借用某大犇的话讲就是,“主席树难不是在于它自身,而是难在于如何把一道题跟它扯上关系”

下面进入正题:

在某些题目中,我们可能需要不断地对线段树修改,并且有可能需要查询的是某一次修改前的事情,而在线段树中,修改即意味着是数据丢失,是难以查询到从前的东西。而可持久化的基本理念就是不将其修改,而是扩建。

初步的想法是对于一次修改就重新搞一棵树出来,但是这在空间上是极度不允许的。我们能够联想到,对于一次修改,复杂度是log(n)级别的,这说明了一次修改所涉及到的区间只有log(n)个,故我们没有必要每次完整地建一棵线段树,只需要新建log(n)个被修改的区间,其他的未被操刀过的区间借用前者的区间即可。每一次修改扩建log(n)个,这是能够勉强接受的。

在此顺便注一句:一定要计算好空间!!!不要像我一样空间算错了开太小然后查了一小时错都没查出来!!!!!!!!后来跟标程一字一字进行了一场“代码优先性逐行逐字比较型工程”才发现标程空间比我多了一点点……

 

【代码环节】

例题:洛谷P3834

这是我阅览了十多份代码中,风格最为人性化的一种


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<algorithm>
#include<iostream>
#define mid (l+r)/2
#define N 200005
using namespace std;

struct node
{
    int val,id;
};

struct chariman
{
    int l,r;
    int sum;   
}tree[N*20];

bool cmp(node aa,node bb)
{
    return aa.val<bb.val;
}

int n,q,a[N],root[N],cnt;
node b[N];

void updata(int &st,int l,int r,int p)
{
    tree[++cnt]=tree[st];
    st=cnt;
    tree[st].sum++;
    if (l==r) return;
    if (p<=mid) updata(tree[st].l,l,mid,p);
        else updata(tree[st].r,mid+1,r,p);
    return;
}

int query(int i,int j,int k,int l,int r)
{
    if (l==r) return l;
    int ltot=tree[tree[j].l].sum-tree[tree[i].l].sum;
    if (k<=ltot) return query(tree[i].l,tree[j].l,k,l,mid);
            else return query(tree[i].r,tree[j].r,k-ltot,mid+1,r);
}

int main()
{
    scanf("%d %d",&n,&q);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&b[i].val);b[i].id=i;
    }
    sort(b+1,b+1+n,cmp);
    for (int i=1; i<=n; i++) a[b[i].id]=i;
    for (int i=1; i<=n; i++)
    {
        root[i]=root[i-1];
        updata(root[i],1,n,a[i]);
    }
    int x,y,k;
    while (q--)
    {
        scanf("%d %d %d",&x,&y,&k);
        printf("%d\n",b[query(root[x-1],root[y],k,1,n)].val);
    }
    return 0;
}

【PAUSE】