//Source：https://blog.csdn.net/Razhme/article/details/80709794
//转自自己的Blog
人的知识就好比一个圆圈，圆圈里面是已知的，圆圈外面是未知的。你知道得越多，圆圈也就越大，你不知道的也就越多。——芝诺*
线段树以其特点能被用来解决许多的问题，其拓展性极强。故学好、用好线段树对增加你的代码长度有显著作用。这篇简小的文章，就来讲一讲线段树的一种变式——可持久化线段树（又作主席树、函数式线段树等）。
先来说一下思想。线段树作为一个二叉树，在其高效的时间效率之外，空间冗余显得不可忽视。一些时候，由于题目中需要寻找数据的区间如火般跳动，线段树常常不是一个，而是连续的很多个。它们出现的顺序普遍是下标，形象一点就是时间顺序。常常是后面的包含前面，但每往后一个，它都会增加一些内容。这时，创建多个是不可免的，空间的需求也快速增加。常常，简单的思想成就了伟大事物的出现。讲到这里，前缀和当然就迫不及待地从意识中钻了出来。可持久化的意义也随之而来：我们将每一棵新的线段树建在其前辈的高台上。最终办法是：用相同的子树表示相同的部分，即将一条链连过去；用不同的新的小的子树表示不同的部分，即增加一条不大的链。
例题-Easy
Source [Poj2104](http://poj.org/problem?id=2104)
给出长度为10w的序列及5k个对于指定区间内第k大的数的询问。
Solution
小学老师曾经说过，对于找规律的题目，不要慌张，不要着急，要从最简单的开始找。所以我们先抛开跳动的区间，对于这输入样例整个地来看。首先，要找第k大的数，必定会想到权值线段树。这样的话，如果右子节点的权值大于等于k，就过去找；反之，就去左边找。找到的根节点就是第k大的数。
现在，我们脚踏家园，放眼世界。对于跳动的区间，根据我们伟大的思想，有这样的发现：要某区间的权值线段树，每个节点的值就是它在[1,r]这棵树中的值减去它在[1,l-1]这棵树中的值。每次查找减一下就是我们需要的这棵树的值了。尽管我们并没建这棵树，却可以用极高的效率间接得出它的信息。
在实现的时候，由于数据的不可预测性，建议使用离散化的数据。建树的过程是这样的：首先，对于每个[1,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
这个庞大的树的空间大概要开数十倍之数据。
我的读入优化出现了小问题，导致无数次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)
给出长度为5w的序列及1w个对于指定区间内第k大的数的询问或对指定数的修改。
