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

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

下面进入正题:

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

初步的想法是对于一次修改就重新搞一棵树出来,但是这在空间上是极度不允许的。我们能够联想到,对于一次修改,复杂度是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】

主席树

主席树又称函数式线段树,就是通过函数来实现的线段树,可以处理一些神奇的问题。

【例题】K-th Number

  • 很明显,这题的数据是不允许对于每一个询问进行一次排序的。那么,考虑一种解法,建你n棵线段树,第i棵线段树维护的是1~i中,大小属于[1,m]的数的数量(1 <= m <= max)。对于每次询问的L,R区间中的第k小数,便可以通过log(n)的时间来完成。
  • 显然我们不能直接全部建出来, 这样时空复杂度都不允许。我们发现相邻的两棵线段树的差别只是i比i-1多了a[i]这个数, 而在权值线段树中多出这样一个值, 第 i 棵树
    与第 i -1棵树的差别实际上只有log 个节点。 也就是我们可以看做在第 i -1
    棵权值线段树中插入权值a[i] 得到第 i 棵权值线段树, 而单点插入过程中只会遇到以及修改根到那个叶子路径上的log(n)个节点。
  • 假设我们已经得到了第 i -1棵权值线段树, 现在要在第i -1棵的基础上加入权值
    a[i]来得到第i 棵树。 首先我们新建一个节点来表示第i 棵树的根节点, 接着我们从第i -1棵以及第i棵树的根节点开始考虑。 对于当前节点, 若当前插入的值a[i] 在当前权值区间中的左半部分,说明a[i] 它要影响第 i 棵树当前节点的左子树的值, 则我们新建一个左儿子, 作为第 i 棵树对应的当前节点左儿子; 而第i 棵树对应的当前节点右儿子( 子树) , 它( 们) 并不受新插入的值的影响, 因此它与第 i -1棵树的当前节点的右儿子( 子树) 的信息一模一样, 所以我们考虑直接将第 i 棵树对应的当前节点右儿子设为第i -1棵树的当前节点的右儿子。 反之亦然。
    插入的代码如下:

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void add(int &cnt, int last, int l, int r, int v)  {
        cnt = ++tot;
        tr[cnt] = tr[last];
        tr[cnt].sum++;
        if (l < r)  {
            if (v <= (l + r) / 2) add(tr[cnt].ls, tr[last].ls, l, (l + r) / 2, v);
            else add(tr[cnt].rs, tr[last].rs, (l + r) / 2 + 1, r, v);
        }
    }

那么对于每一个询问,代码就显而易见了:


1
2
3
4
5
6
7
int que(int pas, int now, int l, int r, int k)  {
    if (l == r) return l;
    int s = tr[tr[now].ls].sum - tr[tr[pas].ls].sum;
    if (k <= s) return que(tr[pas].ls, tr[now].ls, l, (l + r) / 2, k);
    return que(tr[pas].rs, tr[now].rs, (l + r) / 2 + 1, r, k - s);

}

具体代码如下:

继续阅读主席树

[BZOJ 1901] Dynamic Rankings

树状数组套主席树。

考虑无修改求区间第 K 大的情况:因为主席树之间支持相加减,故可以维护一些包含 1~i 的线段树,计算它们的树前缀和,从而快速得到区间 [l, r] 中的第 K 大数。

考虑对于数的静态区间和与动态区间和的关系——前缀和与树状数组。

类似地,我们可以维护一个树状数组,但线段树记录的不再是前缀和,而是树状数组的辅助数组的值。

这样就能做到带修改的区间第 K 大值查询了。

Reference:

http://blog.csdn.net/u014664226/article/details/47839973

代码如下:

继续阅读[BZOJ 1901] Dynamic Rankings

BZOJ2588 Spoj 10628. Count on a tree

BZOJ2588

求树上路径上节点权值k小。

可以发现树上两点u,v之间的第k小点权等价于(root <-> u) + (root <-> v) - (root <-> lca(u, v)) - (root <-> father[lca(u, v)])上的第k小点权,其中root为根节点,lca(u, v)为u和v的最近公共祖先,father[lca(u, v)]为lca(u, v)的父节点。

那么可以维护root到所有节点的权值,显然root到某个点x的权值和root到x父节点的权值只有点x这个点权的差别,那么可以用主席树维护这个东西了。

继续阅读BZOJ2588 Spoj 10628. Count on a tree

[FJOI2016]神秘数

神秘数。同BZOJ4299

10%:枚举每个数字作为神秘数,搜索判断

30%:显然可以发现一个性质:假设当前神秘数为ans,那么可以被表示的区间为[1, ans - 1]。若加入一个数x,且x满足1xans + 1,则神秘数变为ans + x。初始的神秘数为0。那么对于每个询问,将区间内的数排序,依次判断即可。

60%:迷之写法,或者是写丑的100%。

100%:30%的方法不容易维护,考虑对于一个数x,若x不可被表示,条件为区间内所有小于x的数的和小于x,这个东西可以用树套树或者主席树维护。(看神犇们的代码好像可以不用离散化,时间少一个log

继续阅读[FJOI2016]神秘数

第K小的数

第K小的数

维护不带修改的区间第k小,分块,划分树都可以做。

然而最常用的是以下做法:主席树或可持久化线段树(我也不知道二者有什么差别。

对于每个区间[1,i]建立一棵权值线段树,显然它与[1,i-1]的差别只有一条链,那么只要建立那条链上的节点就可以了。

继续阅读第K小的数