title: Tree-structure
date: 2019-05-21 21:21:25
tags: 算法
树形结构
<!--more-->
二叉树
四种遍历方式：
- 先序遍历二叉树顺序：根节点 –> 左子树 –> 右子树，即先访问根节点，然后是左子树，最后是右子树。
上图中二叉树的前序遍历结果为：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 - 中序遍历二叉树顺序：左子树 –> 根节点 –> 右子树，即先访问左子树，然后是根节点，最后是右子树。
上图中二叉树的中序遍历结果为：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 - 后续遍历二叉树顺序：左子树 –> 右子树 –> 根节点，即先访问左子树，然后是右子树，最后是根节点。
上图中二叉树的后序遍历结果为：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1 - 层序遍历二叉树顺序：从最顶层的节点开始，从左往右依次遍历，之后转到第二层，继续从左往右遍历，持续循环，直到所有节点都遍历完成 。
上图中二叉树的层序遍历结果为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
给出前序和中序输出后序
POJ 2255 Tree Recovery
char pre_order[MAXN];
char in_order[MAXN];
void build(int n,char *pre_order,char *in_order){
if(n<=0)return;
else{
int p=strchr(in_order,pre_order[0])-in_order;
build(p,pre_order+1,in_order);
build(n-1-p,pre_order+p+1,in_order+p+1);
printf("%c",pre_order[0]);
}
}
int main(){
while(scanf("%s %s",pre_order,in_order)!=EOF){
int n=strlen(pre_order);
build(n,pre_order,in_order);
printf("\n");
}
}构建一棵二叉树
洛谷 P1305 新二叉树
struct Tree{
char node;
Tree* left=NULL;
Tree* right=NULL;
} tree;
Tree* build(char leave){
if(leave=='*') return NULL;
Tree* newnode=new Tree;
newnode->node=leave;
return newnode;
}
Tree* find(char rt,Tree* start=&tree){
if(start->node==rt) return start;
Tree* ans=NULL;
if(start->left) ans=find(rt,start->left);
if(ans) return ans;
if(start->right) ans=find(rt,start->right);
return ans;
}
void traverse_preorder(Tree* start=&tree){
cout<<start->node;
if(start->left) traverse_preorder(start->left);
if(start->right) traverse_preorder(start->right);
}
int main(){
int n;cin>>n;
char rt,l,r;cin>>rt>>l>>r;
tree.node=rt; tree.left=build(l); tree.right=build(r);
fin(i,1,n){
char rt,l,r;cin>>rt>>l>>r;
Tree* node=find(rt);
node->left=build(l);
node->right=build(r);
}
traverse_preorder();
cout<<endl;
return 0;
}判断对称二叉树
洛谷 P5018 对称二叉树
const int the_MAXN=1e6+5;
int n,tree[the_MAXN][2],a[the_MAXN],size[the_MAXN];
void dfs(int i){
size[i]+=(tree[i][0]==-1)?0:(dfs(tree[i][0]),size[tree[i][0]]);
size[i]+=(tree[i][1]==-1)?0:(dfs(tree[i][1]),size[tree[i][1]]);
}
bool cheak(int u,int v){
if(u==-1&&v==-1) return true;
if(u!=-1&&v!=-1&&a[u]==a[v]&&cheak(tree[u][0],tree[v][1])&&cheak(tree[u][1],tree[v][0])) return true;
}
int main(){
in(n);
fin2(i,1,n) in(a[i]),size[i]=1;
fin2(i,1,n) in(tree[i][0]),in(tree[i][1]);
dfs(1);
int res=0;
fin2(i,1,n) if(cheak(tree[i][0],tree[i][1])) res=max(res,size[i]);
outln(res); return 0;
}时间复杂度为O(n\log n)。
每层遍历的结点总数为n，层数为树高\log n。
线段树
入门参考
详解参考
引例
有100000个正整数的序列a_i,a_2,...a_{100000}。
修改：将第L个数增加c
统计：编号L到R的所有数之和为多少？
这便是典型的线段树点修改问题。
线段树的存储结构：
- 实现方式：二叉树，数组
- 足够空间：数据大小n的4倍
- 实际需要空间：数据大小n向上扩充到最近的2的某个次方的两倍
- 节点表示：假设某节点的编号为v，那么它左节点编号为2v(又v<<1)，右节点编号为2v+1(又v<<1|1)。规定根节点为1。
- 复杂度：修改和统计的复杂度都是O(\log_2n)
- 具体实现：将每个区间[L,R]分解成[L,M]和[M+1,R]，其中M=(L+R)/2，直到L==R为止。线段树对于每个n的分解是唯一的，所以n相同的线段树结构相同，这也是实现可持久化线段树的基础。
- 图解[1,13]的分解：
实现代码：
//定义************
#define maxn 100007 //元素总个数
int Sum[maxn<<2],Add[maxn<<2];//Sum求和，Add为懒惰标记
int A[maxn],n;//存原数组数据下标[1,n]
//====================================
//建树
//PushUp函数更新节点信息 ，这里是求和
void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}
//Build函数建树
void Build(int l,int r,int rt){ //l,r表示当前节点区间，rt表示当前节点编号
if(l==r) {//若到达叶节点
Sum[rt]=A[l];//储存数组值
return;
}
int m=(l+r)>>1;
//左右递归
Build(l,m,rt<<1);
Build(m+1,r,rt<<1|1);
//更新信息
PushUp(rt);
}
//=====================================
//点修改
void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间，rt表示当前节点编号
if(l==r){//到叶节点，修改
Sum[rt]+=C;
return;
}
int m=(l+r)>>1;
//根据条件判断往左子树调用还是往右
if(L <= m) Update(L,C,l,m,rt<<1);
else Update(L,C,m+1,r,rt<<1|1);
PushUp(rt);//子节点更新了，所以本节点也需要更新信息
}
//======================================
//下推标记
void PushDown(int rt,int ln,int rn){
//ln,rn为左子树，右子树的数字数量。
if(Add[rt]){
//下推标记
Add[rt<<1]+=Add[rt];
Add[rt<<1|1]+=Add[rt];
//修改子节点的Sum使之与对应的Add相对应
Sum[rt<<1]+=Add[rt]*ln;
Sum[rt<<1|1]+=Add[rt]*rn;
//清除本节点标记
Add[rt]=0;
}
}
//=======================================
//区间修改
void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内
Sum[rt]+=C*(r-l+1);//更新数字和，向上保持正确
Add[rt]+=C;//增加Add标记，表示本区间的Sum正确，子区间的Sum仍需要根据Add的值来调整
return ;
}
int m=(l+r)>>1;
PushDown(rt,m-l+1,r-m);//下推标记
//这里判断左右子树跟[L,R]有无交集，有交集才递归
if(L <= m) Update(L,R,C,l,m,rt<<1);
if(R > m) Update(L,R,C,m+1,r,rt<<1|1);
PushUp(rt);//更新本节点信息
}
//=======================================
//区间查询
int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
if(L <= l && r <= R){
//在区间内，直接返回
return Sum[rt];
}
int m=(l+r)>>1;
//下推标记，否则Sum可能不正确，因为在Update((L <= l && r <= R))中的还没有根据标记更新
PushDown(rt,m-l+1,r-m);
//累计答案
int ANS=0;
if(L <= m) ANS+=Query(L,R,l,m,rt<<1);
if(R > m) ANS+=Query(L,R,m+1,r,rt<<1|1);
return ANS;
}
//========================================
//函数调用
// //建树
// Build(1,n,1);
// //点修改
// Update(L,C,1,n,1);
// //区间修改
// Update(L,R,C,1,n,1);
// //区间查询
// int ANS=Query(L,R,1,n,1);例题 HDU-1166 敌兵布阵
线段树的概念：
线段树是擅长处理区间的，形如下图的数据结构。线段树是一颗完美二叉树，树上的每个节点都维护一个区间，根维护的是整个区间，每个节点维护的是父亲结点的区间二等分后的其中一个子区间。当有n个元素时，对区间的操作可以在O(logn)的时间内完成。
根据节点中维护的数据的不同，线段树可以提供不同的功能。
如基于线段树的RMQ结构：
在给定序列a_0,a_1,...a_{n-1}的情况下，可以在O(\log n)时间内完成如下两种操作：
- 给定s和t，求a_s,a_{s+1},...s_t的最值
- 给定i和x，把a_i的值改为x
拓展：ST表实现RMQ
基于稀疏表（Sparse Table）的RMQ算法分为两个部分：
离线预处理O(n\log n)和在线查询O(1)。
1.离线预处理
ST算法使用DP思想求解区间最值，不过区间在增加时，每次并不是增加一个长度，而是使用倍增思想，每次增加2^i个长度。
使用t[i,j]表示以i为起点，区间长度为2^j的区间最值，此时区间为[i,i+2^j-1]。
在求解t[i,j]时，ST算法是先对长度为2^j的区间[i,i + 2^j - 1]分成两等份，每份长度均为2^{j - 1}。之后分别求解这两个区间的最值t[i,i+2^{j - 1}-1]和t[i + 2^{j - 1},j - 1]。最后在结合这两个区间的最值，求出整个区间的最值。当j=0时，区间长度等于1，即区间中只有一个元素，此时t[i,0]应等于每一个元素的值。
状态转移方程： t[i,j] = min(t[i,j - 1],t[i + 2^{j - 1},j - 1])
初始状态为：t[i,0] = a[i]。
在根据状态转移方程递推时，是对每一元素，先求区间长度为1的区间最值，之后再求区间长度为2的区间最值，之后再求区间长度为4的区间最值….
i 1 2 3 4 5 6 7 8
a 5 3 7 9 6 4 1 2
5 3 7 9 6 4 1 2
3 3 7 6 4 1 1
3 3 4 1 1
1
2.在线查询
已知待查询的区间[x,y]，求解其最值。
在预处理期间，每个状态对应的区间长度都是2^i，由于给出的区间长度不一定恰好是2^i，因此我们应对待查询的区间进行处理。
这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：
（1）这两个小区间要能覆盖整个区间
（2）为了利用预处理的结果，要求小区间长度相等且都为2^i。注意两个小区间可能重叠。
如：待查询的区间为[3,11]，先尽量等分两个区间，则先设置为[3,7]和[8,11]。之后再扩大这两个区间，让其长度都等于为2^i。刚划分的两个区间长度分别为5和4，之后继续增加区间长度，直到其成为2^i。此时满足两个条件的最小区间长度为8,此时i = 3。
i=int(log(y-x))
根据上述思想，可以把待查询区间[x,y]分成两个小区间[x,x+2^i-1] 和 [y - 2^i + 1,y] ，其又分别对应着t[x,i]和t[y-2^i+1,i]，此时为了求解整个区间的最小值，我们只需求这两个值得最小值即可，此时复杂度是O(1)。
int stmax[MAXN][32];
int stmin[MAXN][32];
int a[MAXN];
int n,q,l,r;
void init(){
int l=31-__builtin_clz(n);
for(int i=1;i<=n;i++){
stmax[i][0]=stmin[i][0]=a[i];
}
for(int j=1;j<=l;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
}
}
}
int rmq_max(int l,int r){
//if(r<l) return 0;
int k=31-__builtin_clz(r-l+1);
return max(stmax[l][k],stmax[r-(1<<k)+1][k]);
}
int rmq_min(int l,int r){
int k=31-__builtin_clz(r-l+1);
return min(stmin[l][k],stmin[r-(1<<k)+1][k]);
}ST表的单次查询效率比基于线段树的RMQ要高，但是其预处理时的时间复杂度和空间复杂度都达到了O(n\log n)。而且，和基于线段树的RMQ相比无法高效地对值进行更新。
试题1：线段树+RMQ
洛谷 P1198 [JSOI2008]最大数
题解
试题2：线段树+区间乘、加修改
洛谷 P2023 [AHOI2009]维护序列
题解
线段树的区间修改也是将区间分成子区间，但是要加一个标记，称作懒惰标记。
标记的含义：本节点的统计信息已经根据标记更新过了，但是本节点的子节点仍需要进行更新。
即，如果将一个区间的所有值加1，实际上并没有给这个区间的所有值都加上1，而是打个标记，记下来，这个节点包含的区间都需要加1。打上标记后，要根据标记更新本节点的统计信息。比如，如果本节点维护的是区间和，而本节点包含5个数，那么，打上+1的标记之后，要给本节点维护的和+5。这是向下延迟修改，但是向上显示的信息是修改以后的信息，所以查询的时候可以得到正确的结果。有的标记之间会相互影响，所以比较简单的做法是，每递归到一个区间，首先下推标记（若本节点有标记，就下推标记），然后再打上新的标记，这样仍然每个区间操作的复杂度是O(\log(n))。
标记有相对标记和绝对标记之分：
相对标记是将区间的所有数+a之类的操作，标记之间可以共存，跟打标记顺序无关。所以可以在区间修改的时候不下推标记，留到查询的时候再下推。
注意：如果区间修改时不下推标记，那么PushUp函数中，必须考虑本节点的标记。而如果所有区间都下推标记，那么PushUp函数可以不考虑本节点的标记，因为本节点的标记一定已经被下推了（也就是对本节点无效了）。
绝对标记是将区间的所有数变成a之类的操作，打标记的顺序直接影响结果，所以这种标记在区间修改的时候必须下推旧标记，不然会出错。
注意，有多个标记的时候，标记下推的顺序也很重要，错误的下推顺序可能会导致错误。
之所以要区分两种标记，是因为非递归线段树只能维护相对标记。因为非递归线段树是自底向上直接修改分成的每个子区间，所以根本做不到在区间修改的时候下推标记。
非递归线段树一般不下推标记，而是自下而上求答案的过程中，根据标记更新答案。
题意：
给一个长度为n的序列a_1,a_2,...,a_n，有以下三种操作。
- 将区间[l,r]内的数全部乘以一个值
- 将区间[l,r]内的数全部加上一个值
- 询问区间[l,r]内数的和，答案对P取模。
本题思路：
首先，本题需要两个标记Add[],Mul[]，并且有一定的下推顺序。
我们考虑一个数a，并对它进行加法和乘法操作。
Sum Action Add Mul
a (init) 0 1
a +b b 1
a c bc 1c
a +d bc+d 1c
(a1c)+(bc+d)=x (PushDown) 0 1
x e 0e 1e
x +f 0e+f 1e
x *g (0e+f)g 1eg
x(1eg)+(0e+f)g=y (PushDown) 0 1
y 0 0 10
y +h h 10
y(1*0)+h (PushDown) 0 1
关于懒惰标记的自我理解：
懒惰标记实际上就是让子节点暂时处于不更新状态，用的时候再更新，例如总长度是1-10，我们想要对1-6都加3，那么Update()会先找1-10，发现不合适，再找它的左右孩子，发现1<5，说明1-6的区间在1-10的左孩子中，同时6>5，1-6也在1-10的右孩子中，这样依次去找1-6在的区间。但是找到1-5的时候，我们发现整个1-5都在1-6中间，也就是说这一段都要更新，那么我们将1-5的sum值更新了，同时用Add[rt]+=3记录下来1-5中的数字现在每个都要加的数字，但是1-5下边还有1-3,4-5,3-3,4-4,5-5，这些我们就可以不用更新，因为这些我们暂时还用不到，假如现在又要将1-5区间的值都加5，那么visit[rt]+=5,此时就是8了，但是还是不用更新他的子节点，假如我们现在要用到1-3区间了，我们就可以一次性给1-3区间加上8，而不用先加3，再加5，这样懒惰标记就使得每次的递归都少了好多。
本题的核心模块如下：
void PushDown(ll rt,ll ln,ll rn){
Mul[rt<<1]=(Mul[rt<<1]*Mul[rt])%MOD;
Mul[rt<<1|1]=(Mul[rt<<1|1]*Mul[rt])%MOD;
Sum[rt<<1]=(Sum[rt<<1]*Mul[rt])%MOD;
Sum[rt<<1|1]=(Sum[rt<<1|1]*Mul[rt])%MOD;
// if(Add[rt]){
//此处和模板中Add[rt]不为0时不更新不同，因为如果Mul[rt]不为1时，仍需要根据Mul[rt]来对
//Add[rt<<1]和Add[rt<<1|1]来更新
Add[rt<<1]=(Add[rt<<1]*Mul[rt]%MOD+Add[rt])%MOD;
Add[rt<<1|1]=(Add[rt<<1|1]*Mul[rt]%MOD+Add[rt])%MOD;
Sum[rt<<1]=(Sum[rt<<1]+Add[rt]*ln%MOD)%MOD;
Sum[rt<<1|1]=(Sum[rt<<1|1]+Add[rt]*rn%MOD)%MOD;
Add[rt]=0;//清除本节点标记
// }
Mul[rt]=1;//清除本节点标记
}
void Update_ADD(ll L,ll R,ll C,ll l,ll r,ll rt){
if(L <= l && r <= R){
Sum[rt]=(C*(r-l+1)%MOD+Sum[rt])%MOD;
Add[rt]=(Add[rt]+C)%MOD;
return ;
}
ll m=(l+r)>>1;
PushDown(rt,m-l+1,r-m);
if(L <= m) Update_ADD(L,R,C,l,m,rt<<1);
if(R > m) Update_ADD(L,R,C,m+1,r,rt<<1|1);
PushUp(rt);
}
void Update_MUL(ll L,ll R,ll C,ll l,ll r,ll rt){
if(L <= l && r <= R){
Sum[rt]=(Sum[rt]*C)%MOD;
Add[rt]=(Add[rt]*C)%MOD;
Mul[rt]=(Mul[rt]*C)%MOD;
return ;
}
ll m=(l+r)>>1;
PushDown(rt,m-l+1,r-m);
if(L <= m) Update_MUL(L,R,C,l,m,rt<<1);
if(R > m) Update_MUL(L,R,C,m+1,r,rt<<1|1);
PushUp(rt);
} 树状数组
BIT的概念
树状数组(Binary Indexed Tree,BIT)是能够完成下述操作的数据结构。
给定一个初始值全为0的数列a_1,a_2,\cdots,a_n
- 给定i，计算a_1+a_2+\cdots+a_i
- 给定i和x，执行a_i+=x
BIT的结构
BIT使用数组维护下图所示的部分和（如\sum_{a_1}^{a5}=bit[4]+bit[5]）
就是把线段树中不需要的节点去掉后，再把剩余的节点对应到数组中。以1结尾的1，3，5，7的长度是1，最后有一个0的2，6长度是2，最后有2个0的4长度为4\cdots\cdots这样，编号的二进制就能够和区间非常容易地对应起来。利用这一性质，BIT可以通过非常简单的位运算实现。
BIT的求和
计算前i项的和需要从i开始，while(i>0){sum+=bit[i];i-lowbit(i);}
BIT的值的更新
使第i项的值增加x需要从i开始，while(i<=n){bit[i]+=x;i+lowbit(i);}
BIT的复杂度
O(\log n)
BIT的实现
int bit[MAX_N+1]；
int lowbit(int i){
return i&-i;
}
int bit_sum(int i){
int s=0;
while(i>0){
s+=bit[i];
i-=lowbit(i);
}
return s;
}
void add(int i,int x){
while(i<=n){
bit[i]+=x;
i+=lowbit(i);
}
}试题1：树状数组+离线查询
洛谷 P1972 [SDOI2009]HH的项链
题解
题意：
给定一个序列a_1,a_2,...,a_n，m次查询区间[l,r]内有多少个不同的数。
N\leq 500000,M\leq 500000,0\leq a_i\leq 1000000
Input 6 1 2 3 4 3 5 3 1 2 3 5 2 6 Output 2 2 4
思路：
对于每个查询区间[l,r]，其中相同的数可以按最右边记录。例如样例中[3,5]区间中位置3处的3可以视为没有贡献。
对于r确定的情况，可以用树状数组维护[1,r]区间，以序列1 2 1 3为例：
对于第一个1，add(1,1)；表示第一个位置出现了一个不一样的数字，此时树状数组所表示的每个位置上的数字（不是它本身的值而是它对应的每个位置上的数字）是：1 0 0 0
对于第二个2，add(2,1)；此时树状数组表示的每个数字是1 1 0 0
对于第三个1，因为之前出现过1了，因此首先把那个1所在的位置删掉add(1,-1),然后在把它加进来add(3,1)。此时每个数字是0 1 1 0
我们将查询区间的r值升序排序，按照r递增的顺序离线处理树状数组。（因为在r递增的过程中，需要修改前面的值，不能简单的用前缀数组处理，而采用树状数组结构）。
主席树
概念：
主席树，也叫可持久化线段树。
可持久化数据结构思想，就是保留整个操作的历史，即，对一个线段树进行操作之后，保留访问操作前的线段树的能力。
最简单的方法，每操作一次，建立一棵新树，这样对空间的需求会很大。
而注意到，对于点修改，每次操作最多影响int(\log_2(n-1))+2个节点
证明如下：
倒数第二层有2^{h-2}<n个节点故2^{h-2}+1\leq n，h\leq \log_2{n-1}+2，对于每层点修改最多只会影响一个区间。
于是，其实操作前后的两个线段树，结构一样，而且只有int(\log_2(n-1))+2个节点不同，其余的节点都一样，于是可以重复利用其余的节点。
这样，每次操作，会增加int(\log_2(n-1))+2个节点。这样的线段树，每次操作需要\log_2的空间。
引入试题
POJ 2104 K-th Number
给定序列a_1,a_2,...a_n，m次询问区间[l,r]内的第k小。
(1\leq n\leq 100000,1\leq m\leq 5000,1\leq a_i\leq 1e9,a_i\neq a_j)
此处的主席树，是对原来的队列[1,n]的每一个前缀[1,i](1\leq i\leq n)建立一棵线段树，线段树的每一个节点存某个前缀[1,i]中属于区间[l,r]中的数有多少个（如根节点是[1,n]，一共有i个数，sum[root]=i;根节点的左儿子是[1,(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left]=x）。若要查找[i,j]中第k大数时，设某节点x，那么x.sum[j]-x.sum[i-1]就是[i,j]中在结点x内的数字总数。而对每个前缀都建一棵树，会MLE，观察到每个前缀树[1,i]和[1,i-1]只有一条路是不一样的，那么其他的节点只要用前一棵树的节点即可，时空复杂度为O(n\log n)。
注：x.sum[j]表示前缀树[1,j]中x节点管辖的区域内的数的个数
由于主席树的主体是多颗线段树，一般线段树某节点的左右节点为i<<1,i<<1|1，主席树在这一点上有别于一般的线段树，每个父节点他的两个儿子不一定满足这个关系。
首先我们来分析一下对于任意区间，如何求解这个区间的第k小值。我们考虑一个线段树的做法，假如一个区间[l,r]，我们用这个区间内出现的数的个数组成一棵线段树，这是什么意思呢，求某个区间的第k小数，当然与这个区间内有多少数比它小有关。下面举例说明如何来建一棵这样的线段树。如这个区间表示的序列是4,1,3,2，求第2小。其中这棵线段树上的每个结点维护的是这个节点表示区间内的数的个数。
圈内的数字表示这个区间内有多少个数，最后的叶结点表示一个数字，对应上述序列中的一个数。（注意：任意一个长度为N的序列我们都可以把他离散为值域在[1,N]的序列。所以如果序列为1000,233,622,520离散化后也是同样的上述结构）。我们如何寻找第2小呢，因为叶节点从左到右表示的数依次增大。根据这个性质，以及每个节点保存了区间内的数的个数这个信息，我们可以轻易的找出区间第2小，具体做法是，从根节点开始，看看左儿子的个数是不是大于等于2，如果是则一定在左儿子中，于是继续找左子树，反之找右子树（如若找第3小，此时要找右子树，在右子树中找第3-2小），直到找到叶结点为止，然后返回叶结点表示的值即可。
但是多次查询区间第k小。我们每次为某一区间建立一个线段树，这样不仅空间复杂度非常高，而且时间复杂度也非常高，那么我们应该思考一种方法，使得对于每次我们查询不同的区间，我们不需要重新建树，如果这样，时间复杂度和空间复杂度就大大降低了。
对于静态求区间和，我们可以预处理出前缀和sum[i]，在每次求区间[l,r]和时，可以直接用sum[r]-sum[l-1]得到答案。
同样，我们可以利用前缀和思想来解决建树问题，我们只需要建立n棵“前缀”线段树即可，第i棵树维护[1,i]序列，这样我们处理任意区间[l,r]时就可以通过处理区间[1,l-1],[1,r]就行，然后两者处理结果相加相减就可以了。
为什么满足相加减的性质及满足什么样的相加减性质呢？我们分析一下，在前缀树[1,l-1]中如果区间[L,R]中有x个数小于一个数，在前缀树[1,r]中如果区间[L,R]有y个数小于一个数，那么查询区间[l,r]在值域区间[L,R]中就有y-x个数小于那个数了。另外需注意，每棵树的结构都是一样的，都是一棵有n个叶节点的线段树。
利用上述前缀和的思想只是解决了时间复杂度的问题，并没有解决空间复杂度的问题，要解决空间复杂度的问题，需要用到线段树的性质。每更新一个数，与更新之前相比，这棵线段树改变的只有一条链（从根节点到某一叶结点），因为第i棵树和第i-1棵树相比，只是更新了第i个元素，所以这两棵树可以共用很多相同的节点（这也是为什么主席树中儿子节点的编号不是i<<1,i<<1|1的原因）于是这样就可以解决空间复杂度问题。
直接看代码更容易理解，已经加入详尽注释。
int n,m;
int cnt;//节点标号
struct node{
int L,R;//分别指向的左右子树
int sum;//该节点管辖区间范围内数的个数
};
node Tree[MAXN*20];//真实所需的空间应为MAXN*树高
struct value{
int x;//值的大小
int id;//离散之前在原数组中的位置
};
value Value[MAXN];
bool comp(const value& v1,const value& v2){
return v1.x<v2.x;
}
int root[MAXN];//多棵线段树的根节点
int mark[MAXN];//原数组离散之后的数组
//update(mark[i],root[i],1,n);
//num为新插入的数，rt为当前所在结点，[l,r]为它所管理的区间
void update(int num,int &rt,int l,int r){
Tree[++cnt]=Tree[rt];//新开辟了一个结点,它的值和当前所在节点相同,即左右儿子也相同
rt=cnt;//当前所在节点转变为新开辟的这个结点
Tree[rt].sum++;//这个结点由于新多了一个值，所以它管辖范围内的数+1,但它的左右儿子没变
if(l==r) return;//如果此时遍历到了叶子节点，即没有左右子节点，return
int mid=(l+r)>>1;//其管辖区域分为[1,mid]和[mid+1,r]
//因为rt传的是引用，所以在下面的update中的rt不等于上一个update中的rt，又每层只需要更新一个区间，所以每次只会增加层高个新节点
if(num<=mid) update(num,Tree[rt].L,l,mid);//若num<=mid，说明左子节点需要+1
else update(num,Tree[rt].R,mid+1,r);//若num>mid,说明右子节点需要+1
}
//query(root[l-1],root[r],k,1,n)
//此处的i,j分别是[1,l-1]和[1,r]的意思，k为第k小
//l,r为区间[l,r],从[1,n]开始划分
int query(int i,int j,int k,int l,int r){
int d=Tree[Tree[j].L].sum-Tree[Tree[i].L].sum;//表示在Tree[j].L和Tree[i].L管辖范围内的数的个数的差值
if(l==r) return l;//当他们遍历到叶子节点时，可以确定唯一值，则可以返回
int mid=(l+r)>>1;
//如果k<=d说明，说明在[1,mid]值域间内，在前缀树[1,l-1]和[1,r]中的，在值域[1,mid]内的数的差值不满足k
//即在前缀树[1,l-1]中小于mid的数有x个，[1,r]中小于mid的有y个，所以小于mid的数在[l,r]中即为y-x个
//d=y-x,如果k<=d，第k小数在[1,mid]范围内
//如果k>d，那么[1,mid]内的数在[l,r]内不足k个，我们需要在[l,r]区间内找值域在[mid+1,n]中的第k-d小的数
//上述以从root[i]和root[j]开始的状态叙述，在遍历过程中1,n用l,r替代
if(k<=d) return query(Tree[i].L,Tree[j].L,k,l,mid);
else return query(Tree[i].R,Tree[j].R,k-d,mid+1,r);
}
int main(){
in(n);in(m);
fin2(i,1,n) in(Value[i].x),Value[i].id=i;
/*
进行离散化,如
Value.x : 1000,39,911,622
Value.id : 1 2 3 4
sort()后
Value.x : 39,622,911,1000
Value.id : 2 4 3 1
mark 4 1 3 2
相当于将Value.x
转换成了 4 1 3 2
*/
sort(Value+1,Value+n+1,comp);
fin2(i,1,n) mark[Value[i].id]=i;
fin2(i,1,n){
root[i]=root[i-1];
update(mark[i],root[i],1,n);
// fin2(i,1,n<<4){ 帮助了解树的建立过程
// cout<<Tree[i].sum<<" ";
// }
// cout<<endl;
}
int l,r,k;
fin2(i,1,m){
in(l);in(r);in(k);
outln(Value[query(root[l-1],root[r],k,1,n)].x);
}
}对于HDU-2665-Kth number，其有多组测试数据，我们只需加一个init()函数，然后在每个测试数据中调用即可。
void init(){
cnt=0;
root[0]=0;
Tree[0].L=Tree[0].R=Tree[0].sum=0;
}个人理解主席树中的核心点：
- 任意一个长度为N的序列我们都可以把他离散为值域在[1,N]的序列
- 主席树是n棵取前缀[1,i](1\leq i \leq n)构成的线段树，每棵树的结构都是一样的，都是一棵有n个叶节点的线段树。每更新一个数，与更新之前相比，这棵线段树改变的只有一条链（从根节点到某一叶结点），因为第i棵树和第i-1棵树相比，只是更新了第i个元素，所以这两棵树可以共用很多相同的节点（这也是为什么主席树中儿子节点的编号不是i<<1,i<<1|1的原因）。每次更新会增加层高个节点，所以空间复杂度为O(n\log n)。
- 取前缀构建线段树的原因，和前缀数组类似，查询[l,r]中的第k小函数query(root[l-1],root[r],k,1,n)，表明了在前缀树[1,l-1]和[1,r]中查询答案，能查询的原因是，每次(l+r)<<1缩小查询范围，由于它们俩的树形结构是相同的，所以对应的值域也是相同的，可以满足加减规则。在前缀树[1,l-1]中如果区间[L,R]中有x个数小于一个数，在前缀树[1,r]中如果区间[L,R]有y个数小于一个数，那么查询区间[l,r]在值域区间[L,R]中就有y-x个数小于那个数了。根据y-x与k的关系，我们选择遍历左子树还是右子树。
京公网安备 11010502036488号