划分树其实就是以线段树作为原型来构造的。划分树的基本思想就是对于要查找的第K大值的区间【s,t】我们拥有一个初始的区间【st,ed】，先将【st,ed】均匀划分成两个区间，第一个区间的数的最大值不大于第二个区间的数的最小值，并通过判断第二个区间里的在【s,t】里面的数的个数是否大于K来判断这个第K大值在左区间还是右区间，个数大于K则在第二个区间，否则在第一个区间，然后再递归区间查找即可。复杂度由于每一次都是均分的，所以为O(logN)。而每一个均分区间的信息都可以预处理得到，而存下这些预处理信息的便是划分树这样一个数据结构。
首先是预处理均分区间的信息。咱们先需要一个二维数组存每一个区间，由于最多只有O(logN)层，所以开的数组可以为：
（用的名字是partition(划分))
var
par,sum:array[0..maxn,0..20]of longint;（一般数据范围在2^20内，即10^6内）
读入的数据第0层即为初始的。然后我们得划分区间，根据区间的定义实际上就是要咱们找中位数，这里我们就可以先用另一个数组a[]存 par[i][0]，然后我们对那个数组排序，那么对于我们划分的区间【l,r】的区间，其中位数就是a[mid=(l+r)shr 1].
至于为什么正确...可以归纳证明。首先对于区间【1，n】，mid显然为中位数成立。接下来假设对于区间【s,t】成立，那么我们把区间【s，t】划分成【s,mid-1】【mid,t】，那么前一个区间的必然都小于a[mid]，后面的都不小于a[mid]，则由划分树的定义易知前一个区间就对应a【s,mid-1】，所以其中位数就为midd=(s+mid-1)shr 1。证毕。
那么我们找到了中位数，我们对于划分树中深度为dep的【l,r】，它可以划分为深度为dep+1的【l,mid-1】【mid,r】。首先for i:=l to r do,对于每一个数判断它是否不大于a[mid]，如果不大于则划分到右边，即【dep+1】【mid,r】内，否则划分到【dep+1】【l,mid-1】内。然后再递归处理深度为dep+1的每一个区间。
procedure partition(l,r,dep:longint)；//新建区间x，其初始范围为【dep】【l,r】，要在它的基础上新建区间
【dep+1】【l,mid-1】和【dep+1】【mid,r】
var i,ll,rr,mid:longint;
begin
if l=r then exit;(如果划分到只剩下一个了则退出）
mid:=(l+r+1)shr 1;
ll:=l-1;rr:=mid-1;
for i:=l to r do
if (par[dep][i]>=a[mid])and(rr<r) then
begin
inc(rr);
par[dep+1][rr]:=par[dep][i];
{if i=l then sum[dep][i]:=0
else sum[dep][i]:=sum[dep][i-1]
end}
else
begin
inc(ll);
par[dep+1][ll]:=par[dep][i];
{if i=l then sum[dep][i]:=1
else sum[dep][i]:=sum[dep][i-1];}
end;
partition(l,mid-1,dep+1);
partition(mid,r,dep+1);
end;
顺便的，在划分的过程中，我们再维护一个sum域，sum【dep,i】表示深度为dep的被包含在区间【l,r】的数par【dep】【i】到其之前的par【dep】【l】间，共有多少数被划分到左区间。这一个东西是日后查找的关键。这个在上面程序的{}处。
然后就是查找了。咱们的过程包含以下六个参数st,ed,dep,s,t,k，其含义为在划分树的区间【dep】【st,ed】中找划分树中【s,t】的第K大值。
function find(st,ed,s,t,k:longint):longint;
var i:longint;
关键在于如何查找。这就需要我们之前用到的sum【】数组。对于区间【st,ed】显然对于被划分到同一个区间的，它们必然是相邻的。所以我们递归下去查找时要找的也是连续的区间。我们知道,sum【dep】【st-1】表示【s,st-1】中进入左区间的数的个数，sum【dep】【ed】表示的就是【s,ed】进入左区间的个数。那么【st,ed】中进入左区间的就是sum【dep】【ed】-sum【dep】【st-1】，如果个数<ed-st+1-k,那么第K大值就在右区间，否则在左区间。那么就这样递归下去即可。
评论