可持久化线段树学习笔记

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭

可持久化线段树的本质是很多棵形态完全相同的线段树。

也可以理解成是，保存了不同时刻版本的线段树的数据结构。

如果没有可持久化线段树，那么我们如果需要不同时刻的线段树，无脑的做法可能是，需要多少个时刻的线段树，就建多少棵线段树。

但是空间绝对gg，我们考虑每次修改，其实对于一次修改，线段树上只有很少一部分被修改了，其他部分都一样。

因此，我们很容易想到，我们何不只考虑修改的部分，其他部分共用，以减少时间和空间消耗呢？

1  * 可持久化线段树是利用函数式编程的思想，对记录的数据只赋值不修改，每次插入一个数据后保存一个历史版本，然后利用线段树的结构完全相同，可以直接相减的特性进行区间询问。

可持久化线段树有几个经典应用，比如求区间第k大静态区间第k大动态区间第k大

静态区间第k大的思想：

* 首先,给你一颗值为横坐标的线段树,每个节点上存着该值出现了多少次,这样的一颗线段树你会求区间k大值吧.二分即可.
* 然后,假设区间是数组arr[n],区间长度是n,那么给你n颗线段树,第i颗线段树是第i-1颗线段树插入arr[i]得到.
* 如果你有了这n颗线段树,想求区间[l,r]中的第k大值,那么你需要在第r颗和第l-1颗线段树的**差线段树**上作二分,就可以求得区间第k大值.
* 差线段树很好理解,比如你有一个部分和数组sum,sum[r]-sum[l-1]就是部分和的差,代表区间[l,r]的和,差线段树同理.
* 现在,可持久化线段树出现为你解决最后一个问题,空间问题.内存很小,不能够存下n颗线段树,但是,第2条中提到,由于第i颗线段是是第i-1颗线段是插入仅一个值得到的,两颗线段树的区别不大,仅有log(n)个节点发生了改变,我们仅仅需要记录这log(n)的数据就可以记录这个增量,这就是可持久化线段树.

以及求区间中不同数的个数 spoj-dquery 求区间中不同数的个数

思想其实和离线线段树是一样的。

在学习可持久化线段树的时候，遇到过一个叫"权值线段树“的概念

其实并不是什么新东西，只不过是把值作为节点来考虑，参考逆序对的线段树|树状数组求法…（由于是在值域上建立线段树，所以常常需要离散化）

~~这思想不是很常见么….感觉完全没必要安个名字…以及，怎么不给BIT也起个叫权值BIT啊orz~~

参考资料：

知乎-主席树是如何求区间k大的？

可持久化数据结构之主席树

spoj DQUERY - D-query (询问区间中不同数的个数，线段树(离线) or 莫队算法（离线） or 主席树（在线）)

Sep 17, 2016·1326 words·3 mins

ACM 主席树分块可持久化数据结构线段树莫队算法

题目链接题意：给出 n 个数，然后 m 个询问，每个询问一个区间 [l,r]，问该区间中不同的数有多少个。思路：离线处理+线段树的做法不多说了：代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST 4File Name :code/spoj/dquery.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=3E4+7; 32const int M=2E5+7; 33int n,Q; 34int a[N]; 35int tree[N<<2]; 36map<int,int>mp; 37struct node 38{ 39 int l,r; 40 int id; 41 bool operator < (node b)const 42 { 43 if (r==b.r) return l<b.l; 44 return r<b.r; 45 } 46}q[M]; 47void PushUp( int rt) 48{ 49 tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 50} 51void update( int p,int sc,int l,int r ,int rt) 52{ 53 if (l==r) 54 { 55 tree[rt]+=sc; 56 return; 57 } 58 int m = (l+r)>>1; 59 if (p<=m) update(p,sc,lson); 60 else update(p,sc,rson); 61 PushUp(rt); 62} 63int query(int L,int R,int l,int r,int rt) 64{ 65 if (L<=l&&r<=R) return tree[rt]; 66 int m = (l+r)>>1; 67 int ret = 0 ; 68 if (L<=m) ret += query(L,R,lson); 69 if (R>=m+1) ret+=query(L,R,rson); 70 return ret; 71} 72int ans[M]; 73int main() 74{ 75 #ifndef ONLINE_JUDGE 76 freopen("code/in.txt","r",stdin); 77 #endif 78 cin>>n; 79 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 80 cin>>Q; 81 for ( int i = 1 ; i <= Q ; i++) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i ; 82 sort(q+1,q+Q+1); 83 int cur = 1; 84 for ( int i = 1 ; i <= Q ; i++) 85 { 86 for ( ; cur <= q[i].r ; cur++) 87 { 88 if (mp[a[cur]]) update(mp[a[cur]],-1,1,n,1); 89 mp[a[cur]] = cur; 90 update(mp[a[cur]],1,1,n,1); 91 } 92 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1); 93 } 94 for ( int i = 1 ; i <= Q ; i++) printf("%d\n",ans[i]); 95 #ifndef ONLINE_JUDGE 96 fclose(stdin); 97 #endif 98 return 0; 99} 之后补一个主席树的做法

Related