可持久化线段树 - 老官童鞋gogo的博客

[card title=“主席树” color=“info”]主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树[/card]

可持久化线段树简介

基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树

总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。

优点解释

每次插入操作最多创建的节点数都为（从根到叶子），一共执行了次插入操作，可持久化线段树的节点总数为，而棵单独的线段树的总节点数是，很明显，可持久化线段树通过重用减少了很多节点。同时，可以查询每个历史版本，查询每个历史版本，查询插入第个元素后的线段树，只需要找到第棵树的树根即可。

可持久化线段树基本操作

数据离散化

因为权值线段树的节点范围是一个值域，因此在值域非常大的时候需要进行离散化处理。

离散化过程很简单，先将a[]中的元素复制一份到，再将中所有数字排序（），去重（），最后使用lower_bound()将原序列转换为去重后序列的下标即可。

建立

创建可持久化线段树的过程，相当于把中的每个元素都离散化为下标，将该下标插入主席树中。

1
for(int i=1;i<=n;i++)
2
{
3
    update(rt[i],rt[i-1],1,tot,lower_bound(b+1,b+tot+1,a[i])-b);
4
}

这里的函数是插入函数，具体操作在下一板块，先了解一下每个参数所表示的意思。其中表示当前版本（第棵树）的树根，为前一版本（第棵树）的树根，为离散化后的元素个数，lower_bound(b+1,b+tot+1,a[i])-b是将离散化后的下标。

因为这里我们用了前缀和的思想，所以是一棵空树，所以我们可以不去建树。

插入操作

简单叙述

插入元素时，只需要创建更新的节点，对无须更新的节点重用上一个版本（注意：不可对历史版本进行修改）。

例如，原序列，利用插入操作创建主席树，排序去重后，，元素个数。原序列的第个元素为，对应的的下标为；第个元素为，对应的下标为，以此类推。最终离散化后的原序列对应的的下标序列为，将该序列插入主席树中。

具体过程

插入元素。复制上一版本，树根区间为，权值加，，这里，将其插入左子树中；复制上一个版本的节点，权值加，，这里，将其加入左子树中，复制上一个版本的节点，权值加。此时已经加到了叶子节点，处理完毕。
插入元素。复制上一版本，权值加，，这里，将其插入左子树；复制上一版本的节点，权值加，，，将其插入左子树；复制上一版本的节点，权值加，，，将其插入左子树；复制上次版本的节点，权值加.此时已经加到了叶子节点，处理完毕。

1
void update(int &i,int j,int l,int r,int k)
2
{
3
  i=++cnt;
4
  tree[i]=tree[j];
5
  tree[i].num++;
6
  if(l==r)
7
    return;
8
  int mid=(l+r)>>1;
9
  if(k<=mid)
10
    update(tree[i].lc,tree[j].lc,l,mid,k);
11
  else
12
    update(tree[i].rc,tree[j].rc,mid+1,r,k);
13
  return;
14
}

其中表示当前版本的父亲节点，表示上一版本的父亲节点，表示当前区间左端点，表示当前区间右端点，表示要插入的值。

可持久化线段树应用

求区间第小的数

原理

在可持久化线段树中，有相同值域的节点有可减性。

以为根的线段树，其权值表示序列有有多少个数落入了区间。
以为根的线段树，其权值表示序列有多少个数落入了区间。

两棵线段树的值域划分是相同的，即两棵线段树中的节点是一一对应的。有相同值域的节点有可减性。的权值减去的权值等于序列有多少个数落入值域区间。

查询[i,j]区间第k小元素的时候，只需要将和两棵线段树的权值相减，就可以得到一棵区间对应的线段树，然后在该线段树上搜索即可。

步骤

当我要查询区间的第小的数，从树根和开始，若l==r，则返回；将当前两个节点的左子树权值相减得到，如果，则在左子树中查找第小，否则在右子树中查找第小。

1
int search(int i,int j,int l,int r,int k)
2
{
3
  if(l==r)
4
    return l;
5
  int s=tree[tree[j].lc].num-tree[tree[i].lc].num;
6
  int mid=(l+r)>>1;
7
  if(k<=s)
8
    return search(tree[i].lc,tree[j].lc,l,mid,k);
9
  else
10
    return search(tree[i].rc,tree[j].rc,mid+1,r,k-s);
11
}

分析

区间查询从根节点到叶子节点最多查询个节点，时间复杂度为，次查询的总时间复杂度为，插入个数需要的时间复杂度，插入个数需要的时间复杂度，所以使用主席树求静态区间第小的数总复杂度为。

而线段树套平衡树可以在的时间复杂度内完成这项任务，但它的时间复杂度不如主席树。但是主席树很难用于动态修改，而线段树套平衡树可以。

代码

来源：洛谷：P3834 【模板】可持久化线段树 2

1
#include<iostream>
2
#include<cstdio>
3
#include<algorithm>
4
#include<cstring>
5
#include<cmath>
6
#include<vector>
7
#include<queue>
8
#include<map>
9
#include<set>
10
using namespace std;
11
#define LL long long
12
#define uLL unsigned long long
13
#define reg register
14
#define PI acos(-1.0)
15
#define pb(x) push_back(x)
16
#define mp(a,b) make_pair(a,b)
17
#define fi first
18
#define se second
19
#define pr(x) cerr<<#x<<"="<<(x)<<endl
20
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
21
#define inf 100000000
22
#define N 1000
23
#define M 10000001
24
template<class T>inline void read(T &x)
25
{
26
    x=0;register char c=getchar();register bool f=0;
27
    while(!isdigit(c))f^=c=='-',c=getchar();
28
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
29
    if(f)x=-x;
30
}
31
template<class T>inline void print(T x)
32
{
33
    if(x<0)putchar('-'),x=-x;
34
    if(x>9)print(x/10);
35
    putchar('0'+x%10);
36
}
37
struct Node
38
{
39
  int lc,rc,num;
40
}tree[M];
41
int a[M],b[M],rt[M],n,m,cnt;
42
void update(int &i,int j,int l,int r,int k)
43
{
44
  i=++cnt;
45
  tree[i]=tree[j];
46
  tree[i].num++;
47
  if(l==r)
48
    return;
49
  int mid=(l+r)>>1;
50
  if(k<=mid)
51
    update(tree[i].lc,tree[j].lc,l,mid,k);
52
  else
53
    update(tree[i].rc,tree[j].rc,mid+1,r,k);
54
  return;
55
}
56
int search(int i,int j,int l,int r,int k)
57
{
58
  if(l==r)
59
    return l;
60
  int s=tree[tree[j].lc].num-tree[tree[i].lc].num;
61
  int mid=(l+r)>>1;
62
  if(k<=s)
63
    return search(tree[i].lc,tree[j].lc,l,mid,k);
64
  else
65
    return search(tree[i].rc,tree[j].rc,mid+1,r,k-s);
66
}
67
int main()
68
{
69
  read(n),read(m);
70
  for(int i=1;i<=n;i++)
71
  {
72
    read(a[i]);
73
    b[i]=a[i];
74
  }
75
  sort(b+1,b+1+n);
76
  int tot=unique(b+1,b+1+n)-b-1;
77
  for(int i=1;i<=n;i++)
78
  {
79
    update(rt[i],rt[i-1],1,tot,lower_bound(b+1,b+tot+1,a[i])-b);
80
  }
81
  for(int i=0;i<=n;i++)
82
  {
83
    pr(rt[i]);
84
  }
85
  for(int i=1;i<=m;i++)
86
  {
87
    int l,r,k;
88
    read(l),read(r),read(k);
89
    int ans=search(rt[l-1],rt[r],1,tot,k);
90
    print(b[ans]);
91
    putchar('\n');
92
  }
93
  return 0;
94
}

老官童鞋gogo