概述
算法适用的问题：
划分树是一种基于线段树的一种数据结构，对于给定的一组数据，快速求解给定区间的第K大值，快排本也可以找出第k大的值，但是每次排序后都会打乱原有序列，每次求解后必须恢复原有序列，当给定数据量大，查询次数较多时，时间复杂度令人不太满意，而划分树则使用二分的思想，将给定的数据建立树型结构，进而在树型结构上进行查找，大大降低了时间复杂度。
算法思想（两步）：
1）建树------离线构建整个查询区间的划分树
2）查找------在划分树中查找某个区间中的第K大值
一.离线构建划分树：
首先对于数列区间的数进行排序，中间的位置为mid=(l+r)/2;不大于中间值的划入左子区间，大于中间值的划入右子区间，划入同一区间的数相对序列不改变，在划分的同时对与第i个数记录[L，i]区间有多少个划入左子区间，然后继续对它的左子区间和右子区间继续进行递归建树，直到划分出最后一层的叶节点为止，整个过程自上而下。
建树代码：
int tree[30][10010];//存放树的矩阵，自上而下
int sorted[30];//排序的序列
int n;//数据的个数
void build(int a,int b,int dep){//从a起始到b的位置进行深度为dep的划分
if(a==b){//如a==b，则说明已经划分到单个数据
return ;
}
int mid=(a+b)>>1;
int same=mid-a+1;
for(int i=a;i<=b;i++){//处理中点遇到相同的数据时
if(sorted[mid]>tree[dep][i]){
same--;
}
}
int lpos=a;
int rpos=mid+1;
for(int i=a;i<=b;i++){//进行划分，按照规则，将数据划分到左右区间
if(tree[dep][i]<sorted[mid]){
tree[dep+1][lpos++]=tree[dep][i];
}else if(tree[dep][i]==sorted[mid]&&same>0){
tree[dep+1][lpos++]=tree[dep][i];
same--;
}else{
tree[dep+1][rpos++]=tree[dep][i];
}
}
build(a,mid,dep+1);//递归划分左子区间
build(mid+1,b,dep+1);。。递归划分右子区间
}
a为起始点，b为终止点，dep为深度，初始的起始点为0，终止点为n-1，深度为0，如果a==b，则划分到叶子，返回，否则对当前深度的区间进行划分，same用于统计和中间值相等的有多少个划入左子区间，小于中间值的划如左子区间，大于中间值的划入右子区间，当前深度划分完成后，再分别对当前深度的左子区间和右子区间进行划分，递归划分到不能划分为止。
驱动程序：
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>tree[0][i];
sorted[i]=tree[0][i];
}
sort(sorted,sorted+n);
q<<"sort"<<endl;
for(int i=0;i<n;i++){
cout<<sorted[i]<<"";
}
build(0,n-1,0);
cout<<endl;
cout<<"tree"<<endl;
for(int i=0;i<10;i++){
for(int j=0;j<n;j++){
cout<<tree[i][j]<<"";
}
cout<<endl;
}
return 0;
}
对n个数进行划分，划分后输出划分树
测试数据：
10
1 5 2 3 6 4 7 3 0 0
输出结果
sort
0 0 1 2 3 3 4 5 6 7
tree
1 5 2 3 6 4 7 3 0 0
1 2 3 0 0 5 6 4 7 3
1 0 0 2 3 5 4 3 6 7
0 0 1 2 3 4 3 5 6 7
0 0 0 0 0 3 4 0 0 0
二.（2）查找------在划分树中查找某个区间中的第K大值
在构建划分树时，同时要构建一个toleft标记数组，用toleft【j】【i】来标记第 j 层的第 i 个数之前有多少个元素划分到左子区间；
在大区间里【L，R】中查询子区间【a，b】中的第c大的值，从划分树的根出发，自上而下的查找，如果查询到叶子，则该整数就是该区间的第c大整数，否则区间【L，a-1】有toleft【dep】【a-1】个整数进入下一层左子树区间，区间【L，b】中有toleft【dep】【b】个数进入下一层的左子树，显然有被查询的【a，b】区间有cnt=toleft【L，b】-toleft【L，a-1】个划分至下一层的左子区间，如果cnt>=k则递归查询【L，mid】，否则查询【mid+1，R】
难点：计算被查询的子区间
查询左子树：
newl = L + toleft[ dep ][ a-1 ]-toleft[ dep ][ L-1 ]//新的左子区间边界
Newr = newl + cnt + 1//右子区间的边界
查询右子树：
newr = b + toleft[ dep ][ R ] - toleft[ dep ][ dep ][ b ];//新的右子区间边界
newl = newr - ( r - a - cnt )//左子区间的边界
查询函数代码
int toleft[300][10010];
int query(int L,int R,int a,int b,int dep,int k){
if(a==b){//查询到叶子，即tree【dep】【a】的值为【a，b】区间的第k大的值
return tree[dep][a];
}
int mid=(L+R)>>1;//计算中点
int cnt;
if(a==0){
cnt=toleft[dep][b];
}else{
cnt=toleft[dep][b]-toleft[dep][a-1];
}
//根据情况查询左右区间
if(cnt>=k){
int newl=L+toleft[dep][a-1]-toleft[dep][L-1];
int newr=newl+cnt-1;
query(L,mid,newl,newr,dep+1,k);
}else{
int newr=b+toleft[dep][R]-toleft[dep][b];
int newl=newr-(b-a-cnt);
query(mid+1,R,newl,newr,dep+1,cnt-k);
}
}
驱动函数
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>tree[0][i];
sorted[i]=tree[0][i];
}
sort(sorted,sorted+n);
build(0,n-1,0);
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
cout<<query(0,n-1,a,b,0,c)<<endl;
return 0;
}
查询子区间【a，b】中第c大的值
测试样例
7
1 5 2 6 3 7 4
2 5 3
输出样例
5
例题1：POJ 2104
链接：http://poj.org/problem?id=2104
解题思路：
通过离线构建划分树，反复查询,划分树的典型例题
#include<iostream>
#include<string.h>
#include<algorithm>
#include<fstream>
usingnamespace std;
int n,m;
constint MANX =100010;
int tree[30][MANX]={0};//树
int sorted[MANX];//排序的序列
int toleft[30][MANX];//第i层的前j个数里有多少划分到下一层的左子区间
voidbuild(int l,int r,int dep){
if(l==r){
return;
}
int mid=(l+r)>>1;
int same=mid-l+1;
for(int i=l; i<=r; i++){
if(tree[dep][i]<sorted[mid]){
same--;
}
}
int lpos=l;
int rpos=mid+1;
for(int i=l; i<=r; i++){
if(tree[dep][i]<sorted[mid]){
tree[dep+1][lpos++]=tree[dep][i];
}elseif(tree[dep][i]==sorted[mid]&&same>0){
tree[dep+1][lpos++]=tree[dep][i];
same--;
}else{
tree[dep+1][rpos++]=tree[dep][i];
}
toleft[dep][i]=toleft[dep][l-1]+lpos-l;
}
build(l,mid,dep+1);
build(mid+1,r,dep+1);}intquery(int L,int R ,int l,int r,int dep,int k){
if(l==r){
return tree[dep][l];
}
int mid=(L+R)>>1;
int cnt=toleft[dep][r]-toleft[dep][l-1];
if(cnt>=k){
int newl=L+toleft[dep][l-1]-toleft[dep][L-1];
int newr=newl+cnt-1;
returnquery(L,mid,newl,newr,dep+1,k);
}else{
int newr=r+toleft[dep][R]-toleft[dep][r];
int newl=newr-(r-l-cnt);
returnquery(mid+1,R,newl,newr,dep+1,k-cnt);
}
}
intmain(){
while(~scanf("%d %d",&n,&m)){
for(int i=1; i<=n; i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(1,n,0);
while(m--){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
printf("%dn",query(1,n,a,b,0,c));
}
}
return0;
}
例题2：HDOJ 4417 Super Mario
链接： http://acm.hdu.edu.cn/showproblem.php?pid=4417
解题思路：构建划分树，通过二分查找出小于等于h的个数
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
usingnamespace std;i
nt tree[30][100010];
int toleft[30][100010]={0};
int sorted[100050];
voidbuild(int a,int b,int dep){
if(a==b){
return;
}
int mid=(a+b)>>1;
int same=mid-a+1;
for(int i=a; i<=b; i++){
if(sorted[mid]>tree[dep][i]){
same--;
}
}
int lpos=a;
int rpos=mid+1;
for(int i=a; i<=b; i++){
if(sorted[mid]>tree[dep][i]){
tree[dep+1][lpos++]=tree[dep][i];
}elseif(sorted[mid]==tree[dep][i]&&same>0){
tree[dep+1][lpos++]=tree[dep][i];
same--;
}else{
tree[dep+1][rpos++]=tree[dep][i];
}
toleft[dep][i]=toleft[dep][a-1]+lpos-a;
}
build(a,mid,dep+1);
build(mid+1,b,dep+1);}intquery(int L,int R,int a,int b,int dep,int k){
if(a==b){
return tree[dep][a];
}
int mid=(L+R)>>1;
int cnt=toleft[dep][b]-toleft[dep][a-1];
if(cnt>=k){
int newl=L+toleft[dep][a-1]-toleft[dep][L-1];
int newr=newl+cnt-1;
returnquery(L,mid,newl,newr,dep+1,k);
}else{
int newr=b+toleft[dep][R]-toleft[dep][b];
int newl=newr-(b-a-cnt);
returnquery(mid+1,R,newl,newr,dep+1,k-cnt);
}
}
intsolve(int n,int s,int t,int h){
int ans=0;
int a=1;
int b=(t-s)+1;
int mid;
while(a<=b){
mid=(a+b)>>1;
int temp=query(1,n,s,t,0,mid);
if(temp<=h){
ans=mid;
a=mid+1;
}else{
b=mid-1;
}
}
return ans;
}
intmain(){
int T;
int n,m;
int s,t,h;
scanf("%d",&T);
int iCase=0;
while(T--){
iCase++;
scanf("%d%d",&n,&m);
memset(tree,0,sizeof(int)*30*10010);
for(int i=1; i<=n; i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(1,n,0);
printf("Case %d:n",iCase);
while(m--){
scanf("%d%d%d",&s,&t,&h);
s++;
t++;
printf("%dn",solve(n,s,t,h));
}
}
return0;
}
最后
以上就是爱听歌猎豹为你收集整理的利用树型结构求解问题之一 利用划分树求解区间内的第K大值的全部内容，希望文章能够帮你解决利用树型结构求解问题之一 利用划分树求解区间内的第K大值所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复