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

分类

1667 字

8 分钟

可持久化线段树

2024-09-29

程设计科

/

算法与数据结构

数据结构

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

可持久化线段树简介#

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

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

优点解释#

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

可持久化线段树基本操作#

数据离散化#

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

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

建立#

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

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
}

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

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

插入操作#

简单叙述#

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

例如，原序列 $a[]=\{12,5,15,8,12,20,12,15\}$ ，利用插入操作创建主席树，排序去重后， $b[]=\{5,8,12,15,20\}$ ，元素个数 $tot=5$ 。原序列 $a[]$ 的第 $1$ 个元素为 $12$ ，对应的 $b[]$ 的下标为 $3$ ；第 $2$ 个元素为 $5$ ，对应的下标为 $1$ ，以此类推。最终离散化后的原序列对应的 $b[]$ 的下标序列为 $\{3,1,4,2,3,5,3,4\}$ ，将该序列插入主席树中。

具体过程#

插入元素 $3$ 。复制上一版本 $rt[1]=rt[0]$ ，树根区间为 $[1,5]$ ，权值加 $1$ ， $mid=\frac{1+5}{2}=3$ ，这里 $mid \le 3$ ，将其插入左子树中；复制上一个版本的节点 $[1,3]$ ，权值加 $1$ ， $mid= \frac{1+3}{2} = 2$ ，这里 $mid<3$ ，将其加入左子树中，复制上一个版本的节点 $[1,2]$ ，权值加 $1$ 。此时已经加到了叶子节点，处理完毕。
插入元素 $1$ 。复制上一版本 $rt[2]=rt[1]$ ，权值加 $1$ ， $mid= \frac{1+5}{2} = 3$ ，这里 $1 \le mid$ ，将其插入左子树；复制上一版本的节点 $[1,3]$ ，权值加 $1$ ， $mid= \frac{1+3}{2}=1$ ， $1 \le mid$ ，将其插入左子树；复制上一版本的节点 $[1,2]$ ，权值加 $1$ ， $mid= \frac{1+2}{2}=1$ ， $1 \le mid$ ，将其插入左子树；复制上次版本的节点 $[1,1]$ ，权值加 $1$ .此时已经加到了叶子节点，处理完毕。

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$ 表示上一版本的父亲节点， $l$ 表示当前区间左端点， $r$ 表示当前区间右端点， $k$ 表示要插入的值。

可持久化线段树应用#

求区间第 $k$ 小的数#

原理#

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

以 $rt[i-1]$ 为根的线段树，其权值表示序列 $[1,i-1]$ 有有多少个数落入了 $[l,r]$ 区间。
以 $rt[j]$ 为根的线段树，其权值表示序列 $[1,j]$ 有多少个数落入了 $[l,r]$ 区间。

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

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

步骤#

当我要查询区间 $[i,j]$ 的第 $k$ 小的数，从树根 $rt[j]$ 和 $rt[i-1]$ 开始，若l==r，则返回 $k$ ；将当前两个节点的左子树权值相减得到 $s$ ，如果 $k \le s$ ，则在左子树中查找第 $k$ 小，否则在右子树中查找第 $k-s$ 小。

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
}

分析#

区间查询从根节点到叶子节点最多查询 $\log n$ 个节点，时间复杂度为 $O(\log n)$ ， $m$ 次查询的总时间复杂度为 $O(m \log n)$ ，插入 $1$ 个数需要 $O(\log n)$ 的时间复杂度，插入 $n$ 个数需要 $O(n \log n)$ 的时间复杂度，所以使用主席树求静态区间第 $k$ 小的数总复杂度为 $O((n+m)\log n)$ 。

而线段树套平衡树可以在 $O((n+m) \log^2 n)$ 的时间复杂度内完成这项任务，但它的时间复杂度不如主席树。但是主席树很难用于动态修改，而线段树套平衡树可以。

代码#

来源：洛谷：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
}

可持久化线段树

https://www.laoguantx.cn/posts/persistentsegmentstree/

作者

老官童鞋gogo

发布于

2024-09-29

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

二叉堆

平衡二叉树（Treap）