划分树

有一个多月没更新博客了，惭愧呀！！！说没时间（毕竟每天娱乐的时间都还是保质保量的… ）都是借口，懒才是真的。。。

划分树是基于线段树的一种数据结构，主要用于在 $log\left(n\right)$log(n)内求出序列区间的第K大值；

划分树主要分为两部分，建树和查询。

插个模板例题Poj 2104 K-th Number

建树：
　　建树过程类似于快速排序，所建的树每一层都有n个元素，建树的核心就是根据根节点的信息将下一层分为左右子节点，使得左子节点内的所有元素严格不大于右子节点内的所有元素。也就是说在每次要递归的区间，找到其中位数，小于中位数的放到左子节点内，大于中位数的放到右子节点。
　　同时这样会保证，在同一个节点内，元素的相对位置相比于原序列来说，相对位置没有发生变化（这一点很重要）。但是在分配元素的过程中还存在着一个问题，那就是中位数在需要处理的区间内，可能不止一个，这种情况就要单独分配。所以，根节点所管辖的区间一旦确立，在左右子节点内元素的个数是确定的，所有将中位数按位补充分配到左右字节点内。之后不断递归建树就可以了。

一些数组声明

int a[MAXN];//原数组
int sorted[MAXN];//排序后的数组
int seg[20][MAXN];//划分树数组
int toleft[20][MAXN];//一个重要的辅助数组
//toleft[d][i] 用来表示当前层里面区间[1,i]里面进入左子树的数的个数
//所以toleft[d][r]-toleft[d][l-1]表示在第d层，区间[l,r]进入左子树的数的个数

good luck and have fun!!!

建树代码：

void build(int l,int r,int d)
{
	if(l==r)
		return;
	int m=(l+r)>>1;
	int suppose=m-l+1;
	for(int i=l;i<=r;i++)
		if(seg[d][i]<sorted[m]) suppose--; //记录需要放在左子树的与中位数一样大的个数
	int nl=l,nr=m+1;
	for(int i=l;i<=r;i++)
	{
		if(seg[d][i]<sorted[m]) seg[d+1][nl++]=seg[d][i];
		else if(seg[d][i]==sorted[m]&&suppose) seg[d+1][nl++]=seg[d][i],suppose--;
		else seg[d+1][nr++]=seg[d][i];
		toleft[d][i]=toleft[d][l-1]+nl-l;
	}
	build(l,m,d+1);
	build(m+1,r,d+1);
}

查询：

查询是在每一层的toleft的基础上进行区间的缩小，直到待查询区间缩小为1即为查询结果。

总区间为 $[L,R]$[L,R],待查区间为 $[l,r]$[l,r]； $k$k是第 $K$K大值， $toleft\left[r\right]-toleft[l-1]$toleft[r]−toleft[l−1]为区间 $[l,r]$[l,r]内被分配到左子数的个数， $M=\lfloor (L+R)/2\rfloor$M=⌊(L+R)/2⌋。

如果 $toleft\left[r\right]-toleft[l-1]\>=k$toleft[r]−toleft[l−1]>=k，则说明第k大值一定在左子树。

此时就可以更新递归到的下一层的区间了，首先大区间二分为 $[L,M]$[L,M]，然后考虑小区间，可以确定的是， $[l,r]$[l,r]分配在左子树的元素一定在区间 $[L,M]$[L,M]内。

然后，确定小区间的左边界 $nl=L+toleft\left[d\right][l-1]-toleft\left[d\right][L-1]$nl=L+toleft[d][l−1]−toleft[d][L−1]。其中 $toleft\left[d\right][l-1]-toleft\left[d\right][L-1]$toleft[d][l−1]−toleft[d][L−1]为 $[L,l-1]$[L,l−1]内被分配到左子树的个数，他们不在查找之列，但相对位置不变，这些元素一定排在前面，以此来确定左边界。

基于左边界，右边界就好确定了，因为 $toleft\left[r\right]-toleft[l-1]\>=k$toleft[r]−toleft[l−1]>=k，所以左边界加上 $toleft\left[r\right]-toleft[l-1]-1$toleft[r]−toleft[l−1]−1即可，即 $nr=nl+toleft\left[r\right]-toleft[l-1]-1$nr=nl+toleft[r]−toleft[l−1]−1。

$toleft\left[r\right]-toleft[l-1]\&lt;k$toleft[r]−toleft[l−1]<k时进入右子树，处理方法类似。

good luck and have fun!!!

查询代码：

int query(int L,int R,int l,int r,int k,int d)
{
	if(l==r) return seg[d][l];
	int M=(L+R)>>1;
	int cnt=toleft[d][r]-toleft[d][l-1];
	if(cnt>=k)
	{
		int nl=L+toleft[d][l-1]-toleft[d][L-1];
		int nr=nl+cnt-1;
		return query(L,M,nl,nr,k,d+1);
	}
	else
	{
		int nr=r+toleft[d][R]-toleft[d][r];
		int nl=nr-(r-l-cnt);
		return query(M+1,R,nl,nr,k-cnt,d+1);
	}
}