可持久化線段樹+主席樹+動態主席樹學習筆記
可持久化線段樹
整體還是很容易理解的，網上的教程都挺不錯
可持久化的原理在於， 借用已經建過的線段樹的一部分
比如，我們有一個數列a={12,23,34,45,56,67,78,89}
而我們想要帶修改的維護這個數列中[L,R]的區間和
建一顆正常的、維護a[1]~a[8]區間和的線段樹就能解決了，這樣就是不修改的情況
問題在於，如果想在這個的基礎上 維護歷史版本 ，應當如何處理？
假設第一次修改，將a[3]改為90
如果我們據此重新建立一顆線段樹，可以發現，只有很少的節點跟初始的線段樹有出入
如果說的更加確切，有出入的節點為 被修改點及其所有祖先
所以，我們建立一顆新的線段樹，相當於 向某個歷史版本插入一條長度為logN的鏈
而對於這條鏈，每個節點的一個兒子一定指向一個沒有出入的區間（即之前某個歷史版本的節點）、另一個一定指向一個包含點修改的區間（新建立的節點），分開操作一下就行了
這樣，M次操作時，整體的時空消耗是O（N+MlogN）
模板題： 洛谷P3919
雖然是可持久化陣列，但是稍微修改一下（把修改和查詢換成區間）就是可持久化線段樹了
（註釋的是自己一開始犯的兩個錯誤）
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int MAX=1000005;
int sz=1,cnt=0;
struct Node
{
int val,l,r;
Node()
{
val=l=r=0;
}
}t[MAX*25];
int n,m;
int a[MAX];
int id[MAX];
void Build()
{
id[1]=1;
for(int i=1;i<sz;i++)
t[i].l=(i<<1),t[i].r=(i<<1)+1;
for(int i=1;i<=n;i++)
t[i+sz-1].val=a[i];
cnt=(sz<<1)-1;
}
inline void Modify(int k,int x,int l,int r,int y)
{
if(l==r)
{
t[cnt].val=y;//#2: Mistake t[cnt] as t[k]
return;
}
int mid=(l+r)>>1;
if(x<=mid)
{
t[cnt].r=t[k].r;
t[cnt].l=++cnt;
Modify(t[k].l,x,l,mid,y);
}
else
{
t[cnt].l=t[k].l;
t[cnt].r=++cnt;
Modify(t[k].r,x,mid+1,r,y);
}
}
inline int Query(int k,int x,int l,int r)
{
if(l==r)
return t[k].val;
int mid=(l+r)>>1;
return (x<=mid?Query(t[k].l,x,l,mid):Query(t[k].r,x,mid+1,r));
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
while(sz<n)
sz<<=1;
Build();
id[0]=1;//#1: Missing initial situation
for(int i=1;i<=m;i++)
{
int ver,op,x,y;
scanf("%d%d",&ver,&op);
id[i]=++cnt;
if(op==1)
{
scanf("%d%d",&x,&y);
Modify(id[ver],x,1,sz,y);
}
else
{
scanf("%d",&x);
t[cnt]=t[id[ver]];
printf("%d\n",Query(id[ver],x,1,sz));
}
}
return 0;
}
View Code
重點還是真正的應用...比如
主席樹
主席樹又叫函式式線段樹，可以解決的一種問題是 動態區間第k小
就是這道經典題： POJ 2104
網上有些部落格在介紹的一開始講的太本質了，導致反而有點難理解
***注意：線段樹外的區間指的就是元素 位置 的區間，而線段樹內的區間指的是元素離散化後的 數值 的區間***
我們先考慮，如何通過線段樹，知道一個固定數列中第k小的數是多少【雖然這裡的做法顯得很笨，但是是 主席樹的簡化版本 】
我們可以將整個數列先離散化，然後對區間中的每一個數進行統計
例如：數列a={10,20,30,20,50,10,60,40}，離散化後得到b={1,2,3,2,5,1,6,4}
對於數列內每一個離散化後的數，我們建立一個基於數值的 區間和線段樹 統計它的出現次數
（7、8是用來佔位的，可以無視）
這樣，我們可以通過類似 二分 的思想找到第k小，而線段樹的節點已經幫助我們將區間對半切分
假設我們想找區間第7小：
step 1: 區間[1,4]內的數一共出現了6次，所以我們可以直接進入另一區間[5,8]，並且找這個區間中的第1小
step 2: 區間[5,6]內的數一共出現了2次，所以[5,8]中的第1小一定也是[5,6]中的第一小
step 3: 區間[5,5]內的數一共出現了1次，所以5正是[5,6]中的第1小，即整個查詢區間中的第7小
有了這樣的鋪墊，我們可以考慮引入可持久化的部分了
對於詢問的某個區間[L i ,R i ]，我們就相當於在處理 只加入L i 到R i 的元素時候 ，像上面問題一樣的區間第k小
所以為什麼主席樹叫做函式式線段樹：我們可以通過 字首區間的相減 來表示任意區間
用人話說，我們將離散化後的數列b的n個元素依次加入線段樹中，進而產生n+1個歷史版本（第0個歷史版本是空線段樹，其餘依次為對[1,1],[1,2],...,[1,n]內元素的數值統計而成的線段樹）
通過這個方法，我們就能表示區間[Li,Ri]所產生的線段樹了：對於每個節點，用第R i 版本的數值減去第L i -1版本的數值（原理同用字首和求區間和）
於是成功轉化為了上面的問題
（註釋的還是自己的兩個錯誤orz）
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
struct Query
{
int x,y,w,ord;
Query(int a=0,int b=0,int c=0,int d=0)
{
x=a,y=b,w=c,ord=d;
}
};
inline bool operator < (Query a,Query b)
{
return a.y<b.y;
}
const int MAX=100005;
int n,m;
int a[MAX];
int id[MAX];
Query q[MAX];
int idx;
map<int,int> mp;
int rev[MAX];
int sz=1,cnt;
struct Node
{
int val,l,r;
Node()
{
val=l=r=0;
}
}t[MAX*22];
inline void Build()
{
id[0]=1;
for(int i=1;i<sz;i++)
t[i].l=(i<<1),t[i].r=(i<<1)+1;
cnt=(sz<<1)-1;
}
inline void Add(int k,int x,int l,int r)
{
if(l==r)
{
t[++cnt].val=t[k].val+1;
return;
}
int cur=++cnt,mid=(l+r)>>1;//#2: Omit condering the changes of cnt
if(x<=mid)
{
t[cur].r=t[k].r;
t[cur].l=cnt+1;
Add(t[k].l,x,l,mid);
}
else
{
t[cur].l=t[k].l;
t[cur].r=cnt+1;
Add(t[k].r,x,mid+1,r);
}
t[cur].val=t[t[cur].l].val+t[t[cur].r].val;
}
inline int Query(int k1,int k2,int l,int r,int w)
{
if(l==r)
return l;
int mid=(l+r)>>1,suml=t[t[k2].l].val-t[t[k1].l].val;
if(suml<w)
return Query(t[k1].r,t[k2].r,mid+1,r,w-suml);
else
return Query(t[k1].l,t[k2].l,l,mid,w);
}
int ans[MAX];
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);//#1: Missing readin m
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),mp[a[i]]=1;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
it->second=++idx,rev[idx]=it->first;
while(sz<idx)
sz<<=1;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].w),q[i].ord=i;
sort(q+1,q+m+1);
Build();
int j=1;
for(int i=1;i<=n;i++)
{
id[i]=cnt+1;
Add(id[i-1],mp[a[i]],1,sz);
while(j<=m && q[j].y==i)
ans[q[j].ord]=Query(id[q[j].x-1],id[i],1,sz,q[j].w),j++;
}
for(int i=1;i<=m;i++)
printf("%d\n",rev[ans[i]]);
return 0;
}
View Code
（這道題在很早很早以前(指2014年)用暴力艹過去了...當時老師還十分詫異來著hhh）
動態主席樹
上面是簡單的、在固定的陣列上進行查詢的主席樹
如果在查詢的同時支援對陣列的點修改，不就更加NB了嗎？
但是，這個功能的加入並不簡單...又是看了幾個部落格強行理解了好久好久（有些講解對新手不是很友好orz）
首先說明一下，動態主席樹跟靜態主席樹在 資料結構上 已經 有些差距 了：動態主席樹說到底是 線段樹套線段樹 （外層可以簡化為樹狀陣列），而靜態主席樹是 重複利用的線段樹 ，兩者是有一定區別的
但是，動態主席樹用到了和靜態主席樹類似的實現思想，就是維護字首和（元素 數值 的字首和）
在上面的靜態主席樹中，我們使用了可持久化線段樹來維護元素，而每個字首和是一顆線段樹：雖然不同歷史版本的線段樹節點之間有交叉以重複利用，但每個歷史版本都有 唯一且獨立的根節點
這就有點像我們求數列的區間和了：對於一個靜態的陣列a[i]，我們先計算字首和pre[i]=pre[i-1]+a[i]，然後通過pre[R]-pre[L-1]來求[L,R]的區間和；但是如果想求一個帶修改的陣列的區間和，必須使用高階資料結構，例如線段樹/樹狀陣列
在這裡也是相似的，只不過區間中的元素從簡單的數字變成了記錄數值出現次數的線段樹了
於是，我們可以考慮 外層是線段樹/樹狀陣列、內層是記錄數值出現次數的區間和線段樹 這樣的結構
- 外層維護的是元素位置的區間：如果我們想查詢[L,R]的第k小，我們首先找的是外層的對應[1,R]、[1,L-1]字首和的幾段區間（外層的節點，就是內層線段樹的根節點）【外層的線段樹的作用，是為了 幫助我們找到位置區間對應的幾顆內層線段樹 】
- 內層維護的是數值的出現次數：每棵線段樹表示，在根節點對應的外層區間中，每個數值出現的次數
先不談直觀上是O(N 2 )的空間消耗（預設已經以原陣列為基礎初始化過了）：後面會有辦法解決這個問題；考慮一下使用這樣結構的可行性
【修改】
如果將位置p i 的數x修改為y，我們在外層線段樹發現p i 的位置一共被logN個區間（節點）包含；同時，以每個節點為根節點的線段樹中，分別各有logN的節點的值被x、y影響
於是，對於外層每個包含p i 的節點，我們都應該在以其為根節點的內層線段樹中將數值x的次數+1、將數值y的次數-1，並一直更新到內層線段樹的根節點
這樣，一次修改的複雜度是O( (logN) 2 )級別的
【查詢】
如果外層是線段樹，對於每次區間[L,R]的查詢，我們都需要先在外層鎖定僅包含區間[L,R]的內層根節點，這組節點最多有logN個
然後我們就可以轉化為靜態主席樹的簡單版本了，只不過這棵線段樹的每個節點的數值 都是 以這組以節點為根的線段樹 相同位置的節點 的 數值之和 （或者說，我們把這組線段樹直接數值意義上的疊加在一起）
然後就是同上用類似二分的方法求區間第k小，就不再贅述了
如果外層是樹狀陣列，對於每次查詢，我們都需要先在外層分別鎖定僅包含區間[1,L-1]、[1,R]的兩組節點，每組節點最多有logN個
但是疊加成一顆線段樹時，要減去[1,L-1]這組的疊加，加上[1,R]這組的疊加，後面還是一樣的求區間第k小
這樣，一次查詢的複雜度也是O( (logN) 2 )級別的
現在我們回到一開始的問題：如何解決爆炸的空間？
如果把內層線段樹的節點全部事先開好的話，就的確是O( N 2 )的了；但事實上，我們一共能訪問到內層線段樹的多少節點呢？
每次修改（基於原始陣列初始化相當於修改N次），同時間複雜度一樣，是(logN) 2 級別的
每次查詢，仍然同時間複雜度一樣，是(logN) 2 級別的
這樣一來，我們真正能訪問到的，一共也就 N * (logN) 2 個內層線段樹的節點；剩下來的，想都不用想，全是0，對於我們的查詢並不會產生影響
所以，可以通過類似可持久化線段樹的動態開點解決
模板題： 洛谷P2617 （比原出處資料更強，甚至直接卡掉 O(N (logN) 3 ) 的線段樹套平衡樹）
說一下對我的坑點...其實動態主席樹的實現在常數上是沒多大區別的（線段樹和樹狀陣列差不多），我對著自己TLE的程式碼、抱著別人AC的程式碼，反反覆覆查了一天半都沒找到個所以然
然後，發現我的離散化用的是map...在每次修改的時候也是直接用的map來找到離散化後的數（修改時一共呼叫了3N次map：初始、加、減各N次）
將離散化的互相對應關係用陣列重新存了下，時間就直接降到了原來的一半，也就是說：map的常數等於一個logN
細思極恐
不過在這裡強烈推薦樹狀陣列：在外層的各種定位可以直接通過加減lowbit的for迴圈完成，而線段樹需要遞迴
（又註釋了一些制杖bug）
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <map>
using namespace std;
const int MAX=100005;
int tot=1,sz=1;
int t[MAX*400],l[MAX*400],r[MAX*400];
int n,m;
int a[MAX];
inline int lowbit(int x)
{
return x&(-x);
}
inline void Insert(int k,int p,int a,int b,int x)
{
if(a==b)
{
t[k]+=x;
return;
}
int mid=(a+b)>>1;
if(p<=mid)
{
if(!l[k])
l[k]=++tot;
Insert(l[k],p,a,mid,x);
}
else
{
if(!r[k])
r[k]=++tot;
Insert(r[k],p,mid+1,b,x);
}
t[k]=t[l[k]]+t[r[k]];
}
inline void Add(int k,int p,int x)
{
for(int i=k;i<=n;i+=lowbit(i))//#1: Need setting limits
Insert(i,p,1,sz,x);
}
int idx;
map<int,int> mp;
int rev[MAX<<1];//#4: Forget to expand the size
void Build()
{
while(tot<n)
tot<<=1;
for(int i=1;i<=n;i++)
Add(i,a[i],1);
}
int lsz,rsz;
int vl[MAX],vr[MAX];
inline int Query(int a,int b,int x)
{
if(a==b)
return a;
int mid=(a+b)>>1,sum=0;//#2: Counting left value
for(int i=1;i<=lsz;i++)
sum-=t[l[vl[i]]];
for(int i=1;i<=rsz;i++)
sum+=t[l[vr[i]]];
if(sum>=x)//#3: Reverse the operator
{
for(int i=1;i<=lsz;i++)
vl[i]=l[vl[i]];
for(int i=1;i<=rsz;i++)
vr[i]=l[vr[i]];
return Query(a,mid,x);
}
else
{
for(int i=1;i<=lsz;i++)
vl[i]=r[vl[i]];
for(int i=1;i<=rsz;i++)
vr[i]=r[vr[i]];
return Query(mid+1,b,x-sum);
}
}
inline void Locate(int x,int y)
{
lsz=rsz=0;
for(int i=x;i;i-=lowbit(i))
vl[++lsz]=i;
for(int i=y;i;i-=lowbit(i))
vr[++rsz]=i;
}
char op[MAX];
int x[MAX],y[MAX],k[MAX];
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),mp[a[i]]=1;
for(int i=1;i<=m;i++)
{
op[i]=getchar();
while(op[i]!='C' && op[i]!='Q')
op[i]=getchar();
if(op[i]=='Q')
scanf("%d%d%d",&x[i],&y[i],&k[i]);
else
scanf("%d%d",&x[i],&y[i]),mp[y[i]]=1;
}
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
it->second=++idx,rev[idx]=it->first;
while(sz<idx)
sz<<=1;
for(int i=1;i<=n;i++)
a[i]=mp[a[i]];
for(int i=1;i<=m;i++)
if(op[i]=='C')
y[i]=mp[y[i]];
Build();
for(int i=1;i<=m;i++)
if(op[i]=='C')
{
Add(x[i],a[x[i]],-1);//#5: Mistake x[i] as i
a[x[i]]=y[i];
Add(x[i],a[x[i]],1);
}
else
{
Locate(x[i]-1,y[i]);
printf("%d\n",rev[Query(1,sz,k[i])]);
}
return 0;
}
View Code
這樣，可持久化線段樹的概念就算是基本學完了（雖然動態主席樹關聯並沒有那麼大）←說的好像其他可持久化資料結構就會了一樣
真正的難點是將可持久化的思想靈活運用到各種各樣刁鑽的題目當中
有時間的話再補些不錯的題目上來orz
這算是我正式開始學習資料結構的入門吧...雖然都是大佬們隨便玩的東西，我枯了
（完）