划分树（我的体会）
关于划分树，我没有百度，只是听说有这么个东西，可以在 log(n) 的时间内，查找出来区间 [st , en] 的第 k 大的值 ， 再看了一下人家的代码，自己 YY 的，一下的内容全部是原创，绝对的原滋原味，要是和标准的定义有什么出入，欢迎指正，我懒得去百度了，能用来解决问题就行了
一、什么是划分树？
就是给一串数，用类似线段树的结构来存储它，怎么存储？假设我们把父亲表示的区间中的数按照从小到大排了一次序，那么左子树存储的是父亲的前一半的数据，右子树存储的是父亲的后一半的数据，但是，存储的时候，要按照数据在父亲中出现的先后顺序存储
二、怎么查找？
查找是基于建树的，要是明白了怎么建树的，查找的过程可以自己手推出来，就不用我再写了，但是为了方便读者阅读，我还是写一下好了
到了这个地步，我们肯定已经在理论上理解了划分树了
下面，线上一个实现代码，具体是那道题目的忘记了，里面有注释，要是还是没有理解的话，可以根据代码看看：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define INF 0x7fffffff#define EPS 1e-7#define N 210000using namespace std;struct data{ int st,en;} T[4*N];int sorted[N];int to_L[40][N];int val[40][N];void build(int v,int st,int en,int deep) //建树{ T[v].st=st; T[v].en=en; if(st==en) return; //叶子节点 int mid=(st+en)>>1; int same=mid-st+1 , mid_val=sorted[mid]; for(int i=st;i<=en;i++) if(val[deep][i]<mid_val) same--; //寻找有几个中间值属于左儿子 int L=st , R=mid+1; for(int i=st;i<=en;i++) { if(i==st) to_L[deep][i]=0; else to_L[deep][i]=to_L[deep][i-1]; if(val[deep][i]<mid_val || val[deep][i]==mid_val && same>0) //这个值应该分配在左儿子中 { val[deep+1][L++]=val[deep][i]; to_L[deep][i]++; if(val[deep][i]==mid_val) same--; } else val[deep+1][R++]=val[deep][i]; //这个值应该分配在右儿子中 } build(v<<1,st,mid,deep+1); //建左子树 build(v<<1|1,mid+1,en,deep+1); //建右子树}int query(int v,int st,int en,int k,int deep) //询问区间 [st,en] 中的第 k 大的值{ if(st==en) return val[deep][st]; //区间宽度为 1，直接返回 int s1,s2; if(st==T[v].st) s1=0; else s1=to_L[deep][st-1]; //区间 [ T[v].st , st-1 ] 中有 s1 个数分在了左儿子中 s2=to_L[deep][en]-s1; //区间 [st , en] 中有 s2 个数分在了左儿子中 /* 如果 k<=s2 ，即是说，[st , en] 中，排好序的前 k 个数一定是分配在了左儿子中，那么，我们就应该 递归查询左子树，而查询的区间就应该是： left = T[v].st + s1 right = T[v].st + s1 + s2 - 1 而查询的依然是这个区间的第 k 大的数（因为这个区间前 s2 大的数全部在左儿子中，而 k<=s2 ） */ if(k<=s2) return query(v<<1,T[v].st+s1,T[v].st+s1+s2-1,k,deep+1); int b1=(st-1-T[v].st+1)-s1; //区间 [ T[v].st , st-1 ] 中有 b1 个数分配在了右儿子中 int b2=(en-st+1)-s2; //区间 [st , en] 中有 b2 个数分配在了右儿子中 int mid=(T[v].st+T[v].en)>>1; /* 如果 k>s2 ，即是说，[st , en] 中，排好序的前 k-s2 个数分配在了右儿子中， 那么，我们就应该查询的是右子树，而查询的区间就应该是： left = mid + 1 + b1 right = mid +1 + b1 + b2 -1 而查询的是这个区间的第 k-s2 大的数 （因为这个区间前 b2 大的数全部在右子树中，而 k-s2<=b2） */ return query(v<<1|1,mid+1+b1,mid+1+b1+b2-1,k-s2,deep+1);}int main(){ int n,m,st,en,ca=0; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",&val[0][i]); //读入数据的时候顺便建立好第 0 层（根节点）表示的数组 sorted[i]=val[0][i]; } sort(sorted+1,sorted+1+n); //排序，为建树做准备 build(1,1,n,0); //建立根节点是 1 ，根区间是 [1 , n] ，根所在的层编号是 0 的划分树 scanf("%d",&m); printf("Case %d:\n",++ca); for(int i=1;i<=m;i++) { scanf("%d%d",&st,&en); printf("%d\n",query(1,st,en,(en-st+1+1)/2,0)); } } return 0;}