//Source：https://blog.csdn.net/Razhme/article/details/80709794
//轉(zhuǎn)自自己的Blog
人的知識(shí)就好比一個(gè)圓圈，圓圈里面是已知的，圓圈外面是未知的。你知道得越多，圓圈也就越大，你不知道的也就越多。——芝諾*
線段樹以其特點(diǎn)能被用來(lái)解決許多的問(wèn)題，其拓展性極強(qiáng)。故學(xué)好、用好線段樹對(duì)增加你的代碼長(zhǎng)度有顯著作用。這篇簡(jiǎn)小的文章，就來(lái)講一講線段樹的一種變式——可持久化線段樹（又作主席樹、函數(shù)式線段樹等）。
先來(lái)說(shuō)一下思想。線段樹作為一個(gè)二叉樹，在其高效的時(shí)間效率之外，空間冗余顯得不可忽視。一些時(shí)候，由于題目中需要尋找數(shù)據(jù)的區(qū)間如火般跳動(dòng)，線段樹常常不是一個(gè)，而是連續(xù)的很多個(gè)。它們出現(xiàn)的順序普遍是下標(biāo)，形象一點(diǎn)就是時(shí)間順序。常常是后面的包含前面，但每往后一個(gè)，它都會(huì)增加一些內(nèi)容。這時(shí)，創(chuàng)建多個(gè)是不可免的，空間的需求也快速增加。常常，簡(jiǎn)單的思想成就了偉大事物的出現(xiàn)。講到這里，前綴和當(dāng)然就迫不及待地從意識(shí)中鉆了出來(lái)。可持久化的意義也隨之而來(lái)：我們將每一棵新的線段樹建在其前輩的高臺(tái)上。最終辦法是：用相同的子樹表示相同的部分，即將一條鏈連過(guò)去；用不同的新的小的子樹表示不同的部分，即增加一條不大的鏈。
例題-Easy
Source [Poj2104](http://poj.org/problem?id=2104)
給出長(zhǎng)度為10w的序列及5k個(gè)對(duì)于指定區(qū)間內(nèi)第k大的數(shù)的詢問(wèn)。
Solution
小學(xué)老師曾經(jīng)說(shuō)過(guò)，對(duì)于找規(guī)律的題目，不要慌張，不要著急，要從最簡(jiǎn)單的開始找。所以我們先拋開跳動(dòng)的區(qū)間，對(duì)于這輸入樣例整個(gè)地來(lái)看。首先，要找第k大的數(shù)，必定會(huì)想到權(quán)值線段樹。這樣的話，如果右子節(jié)點(diǎn)的權(quán)值大于等于k，就過(guò)去找；反之，就去左邊找。找到的根節(jié)點(diǎn)就是第k大的數(shù)。
現(xiàn)在，我們腳踏家園，放眼世界。對(duì)于跳動(dòng)的區(qū)間，根據(jù)我們偉大的思想，有這樣的發(fā)現(xiàn)：要某區(qū)間的權(quán)值線段樹，每個(gè)節(jié)點(diǎn)的值就是它在[1,r]這棵樹中的值減去它在[1,l-1]這棵樹中的值。每次查找減一下就是我們需要的這棵樹的值了。盡管我們并沒(méi)建這棵樹，卻可以用極高的效率間接得出它的信息。
在實(shí)現(xiàn)的時(shí)候，由于數(shù)據(jù)的不可預(yù)測(cè)性，建議使用離散化的數(shù)據(jù)。建樹的過(guò)程是這樣的：首先，對(duì)于每個(gè)[1,n]的樹，分配一個(gè)根節(jié)點(diǎn)，它直接復(fù)制上一個(gè)根節(jié)點(diǎn)的信息；其次，分配時(shí)相當(dāng)于我們添加了一個(gè)數(shù)，由于這個(gè)節(jié)點(diǎn)連接的是上個(gè)版本可用的信息，我們只需替換修改的那一條鏈，具體操作和普通權(quán)值線段樹相似。
Code for reference
include<iostream>
include<cstdio>
include<algorithm>
using namespace std;
const int N=100005;
struct node
{
int sum,l,r;
};
struct num
{
int n,loc;
};
node tree[N*20];
int tot=0;
num a[N];
int n,m;
int b[N];
int root[N];
bool cmp(num x,num y)
{
return x.n<y.n;
}
void insert(int num,int &now,int l,int r)
{
tree[++tot]=tree[now];
now=tot;
tree[now].sum++;
if(l==r)return;
int mid=l+r>>1;
if(num<=mid)
insert(num,tree[now].l,l,mid);
else
insert(num,tree[now].r,mid+1,r);
}
int query(int i,int j,int k,int l,int r)
{
if(l==r)return l;
int ans=tree[tree[j].l].sum-tree[tree[i].l].sum,mid=l+r>>1;
if(k<=ans)
return query(tree[i].l,tree[j].l,k,l,mid);
else
return query(tree[i].r,tree[j].r,k-ans,mid+1,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i].n);
a[i].loc=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
{
b[a[i].loc]=i;
}
for(int i=1;i<=n;++i)
{
root[i]=root[i-1];
insert(b[i],root[i],1,n);
}
int x,y,z;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",a[query(root[x-1],root[y],z,1,n)].n);
}
return 0;
}
Hint
這個(gè)龐大的樹的空間大概要開數(shù)十倍之?dāng)?shù)據(jù)。
我的讀入優(yōu)化出現(xiàn)了小問(wèn)題，導(dǎo)致無(wú)數(shù)次Runtime Error。
思考題-Easy
Source CQOI2015 [Luogu3168](https://www.luogu.org/problemnew/show/P3168)
例題-Normal
Source [Bzoj1901](http://www.lydsy.com/JudgeOnline/problem.php?id=1901)/[Zoj2112](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112)
給出長(zhǎng)度為5w的序列及1w個(gè)對(duì)于指定區(qū)間內(nèi)第k大的數(shù)的詢問(wèn)或?qū)χ付〝?shù)的修改。
