今晚又学了另外一种树----划分树。看了一晚上了，也是大概明白一些而已，对于一些细节还是不太理解。

划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值 。（主席树也可以，早就听过主席树这个词，感觉好高大上，准备学习一下，下面的例题也是主席树入门）

划分树的定义

         划分树定义为，它的每一个节点保存区间[lft,rht]所有元素，元素顺序与原数组（输入）相同，但是，两个子树的元素为该节点所有元素排序后(rht-lft+1)/2个进入左子树，其余的到右子树，同时维护一个num域，num[i]表示lft->i这个点有多少个进入了左子树。

 

划分树的Sample

 

   如果由下而上看这个图，我们就会发现它和归并排序的（归并树）的过程很类似，或者说正好相反。归并树是由下而上的排序，而它确实是由上而下的排序（观察’4’的运动轨迹，我们可以猜到，划分树的排序也是一种稳定的排序方法，这里不是说明的重点，不予证明），但这正是它可以用来解决第k大元素的理由所在。（具体的理由，写完再补）

划分树的原理

划分树和归并树都是用线段树作为辅助的，原理是基于快排 和归并排序 的。

划分树的建树过程基本就是模拟快排过程，取一个已经排过序的区间中值，然后把小于中值的点放左边，大于的放右边。并且记录d层第i个数之前（包括i）小于中值的放在左边的数。具体看下面代码注释。

查找其实是关键，因为再因查找[l,r]需要到某一点的左右孩子时需要把[l,r]更新。具体分如下几种情况讨论：
假设要在区间[l,r]中查找第k大元素，t为当前节点，lch，rch为左右孩子，left，mid为节点t左边界和中间点。
1、sum[r]-sum[l-1]>=k，查找lch[t],区间对应为[ left+sum[l-1] , left+sum[r]-1 ]
2、sum[r]-sum[l-1]<k,查找rch[t]，区间对应为[ mid+1+l-left-sum[l-1] , mid+1+r-left-sum[r] ]

上面两个关系在纸上可以推出来，对着上图更容易理解关系式

划分树链接：

1划分树

2划分树

3划分树

例题：poj 2104   K-th Number（划分树模板）

给出一个长度为n的数列，询问m次，每次给出a,b,k，询问[a,b]区间内第k大的数

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=100005;
int sorted[N];    // 对原来集合中的元素排序后的值。 
int arr[N];
double Sum=0;
struct tree{
	int val[N];       // val 记录第 k 层当前位置的元素的值 
	int num[N];      // num 记录元素所在区间的当前位置之前进入左孩子的个数 
	double sum[N];    // sum 记录比当前元素sorted[mid]小的元素的和
}t[20];
//划分树构建 
void build(int l,int r,int p){
	if(l==r) return ;
	/* same 用来标记和中间值 sorted[mid] 相等的，且分到左孩子的数的个数。 
	初始时，假定当前区间[lft,rht]有 mid-lft+1 个和 sorted[mid] 相等。    
	先踢掉比中间值小的,剩下的就是要插入到左边的
	例如 1 3 3 3 3 5 5 7   same=4,sorted[mid]=3,分到左孩子且值为3的个数为3 
	*/   
	int mid=(l+r)>>1,same=mid-l+1,lp=l,rp=mid+1;
	for(int i=l;i<=r;i++){
		if(t[p].val[i]<sorted[mid]) same--;
	}
	for(int i=l;i<=r;i++){
		if(i==l){                                  // 初始一个子树。 
			t[p].num[i]=t[p].sum[i]=0;
		}
		else{                                     // 初始区间下一个节点。 
			t[p].num[i]=t[p].num[i-1];
			t[p].sum[i]=t[p].sum[i-1];
		}
		/* 如果大于，肯定进入右孩子，否则，判断是否还有相等的应该进入左孩子的，  
		 没有，就直接进入右孩子，否则进入左孩子，同时更新节点的 sum 域和 num 域*/   
		if(t[p].val[i]<sorted[mid]){
			t[p].num[i]++;
			t[p].sum[i]+=t[p].val[i];
			t[p+1].val[lp++]=t[p].val[i];
		}
		else if(t[p].val[i]>sorted[mid]){
			t[p+1].val[rp++]=t[p].val[i];
		}
		else{
			if(same){
				same--;
				t[p].num[i]++;
				t[p].sum[i]+=t[p].val[i];
				t[p+1].val[lp++]=t[p].val[i];
			}
			else
			    t[p+1].val[rp++]=t[p].val[i];
		}
	}
	build(l,mid,p+1);
	build(mid+1,r,p+1);
} 
//划分树查找 
/* 在区间[a, b]上查找第 k 大元素，同时 Sum 返回区间[a, b]中小于第 k 大元素的和。*/ 
int query(int a,int b,int l,int r,int p,int k){
	int s;                      //[l, a)内将被划分到左子树的元素数目
	int ss;                     //[a, b]内将被划分到左子树的元素数目
	double sss;                 // sss 记录区间[a, b]中小于第 k 大元素的值的和。 
	int mid=(l+r)>>1;
	if(l==r) return t[p].val[a];
	//区间端点点重合的情况,要单独考虑 !!!!!!
	if(a==l){
		s=0;
		ss=t[p].num[b];
		sss=t[p].sum[b];
	}
	else{
		s=t[p].num[a-1];
		ss=t[p].num[b]-s;
		sss=t[p].sum[b]-t[p].sum[a-1];
	}
	 // 进入左孩子，同时更新区间端点值 
	if(ss>=k){
		int la=l+s;
		int lb=l+s+ss-1;
		return query(la,lb,l,mid,p+1,k);
	}
	else{
		int la=mid+1+a-l-s;
		int lb=mid+1+b-l-s-ss;   //lb=la+b-a-num[b]=mid+1+a-l-s+b-a-s-ss
		Sum+=sss;
		return query(la,lb,mid+1,r,p+1,k-ss);
	}
}
int main() {

    #ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int n,m,k,a,b;
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++){
			scanf("%d",&arr[i]);
			t[0].val[i]=sorted[i]=arr[i];
		}
		sort(sorted+1,sorted+n+1);
		build(1,n,0);
		while(m--){
			scanf("%d%d%d",&a,&b,&k);
			printf("%d\n",query(a,b,1,n,0,k));
		}
	}
}