《程序设计解题策略》——第1章 利用树型数据关系的解题策略 1.1 利用划分树求解整数区间内第k大的值

  1. 云栖社区>
  2. 博客>
  3. 正文

《程序设计解题策略》——第1章 利用树型数据关系的解题策略 1.1 利用划分树求解整数区间内第k大的值

华章计算机 2017-06-12 14:46:00 浏览1662
展开阅读全文

本节书摘来自华章计算机《程序设计解题策略》一书中的第1章,第1.1节,作者:吴永辉 王建德 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

第1章 利用树型数据关系的解题策略 

树是一个具有层次结构的集合,一种限制前件数且没有回路的连通图。在现实生活和程序设计的竞赛试题中,许多问题的数据关系呈树型结构,因此有关树的概念、原理、操作方法和一些由树的数据结构支持的算法,一直受到编程者的重视,被广泛应用于解题过程。在本章里,我们将介绍利用树型数据关系解题的七种策略:
1) 利用划分树求解整数区间内第k大值。
2) 利用最小生成树及其扩展形式(最优比率生成树、最小k度生成树、次小生成树)计算有权连通无向图中边权和满足限制条件的最优生成树。
3) 利用线段树计算区间。
4) 利用改进型的二叉查找树(伸展树和红黑树)优化动态集合的操作。
5) 利用动态树维护森林的连通性。
6) 利用左偏树实现优先队列的合并。
7) 利用跳跃表取代树结构,这种策略不失时空效率,容易编程实现。
前六种树型结构鲜见于一般数据结构教材,利用这些特殊类型的树可优化存储结构和算法效率。

1.1 利用划分树求解整数区间内第k大的值

如何快速求出(在log2n的时间复杂度内)整数区间[x,y]中第k大的值(x≤k≤y)?注意,所谓区间指的是整数的序号范围,[x,y]指区间内第x个整数至第y个整数间的y-x+1个整数,而不是指整数值本身。
人们通常会想到采用快速查找法查找整数区间的第k大值,但这种方法会破坏原序列且需要O(n)的时间复杂度,即便使用平衡二叉树进行维护,虽每次查找时间复杂度降为O(log2n),但由于丢失了原序列的顺序信息,也很难查找出某区间内的第k大值。
划分树主要是针对上述问题而设计的。划分树是一种基于线段树的数据结构,其基本思想就是将待查找区间划分成两个子区间:不大于数列中间值的元素被分配到左儿子的子区间,简称左子区间;大于数列中间值的元素被分配到右儿子的子区间,简称右子区间。
显然,左子区间的数小于右子区间的数。建树的时候要注意,对于被分到同一子树的元素,元素间的相对位置不能改变。例如构建整数序列[1 5 2 3 6 4 7 3 0 0]的划分树:
整数序列经排序后得到[0 0 1 2 3 4 5 6 7],中间值为3。划分出下一层的左子区间[1 2 3 0 0],中间值为1;下一层的由子区间[5 6 4 7 3],中间值为5;以中间值为界,划分出当前层每个区间的下层左右子区间……依此类推,直至划分出的所有子区间含单个整数为止(见图1.1-1)。
由图1.1-1可见,划分树是一棵完全二叉树,树叶为单元素区间。若数列含n个整数,则对应的划分树有「log2n+1层。
查找的时候通过记录进入左子树的数的个数,确定下一个查找区间,直至查找范围缩小到单元素区间为止。此时,区间内的第k大值就找到了。
整个算法分两步:
1) 建树——离线构建整个查询区间的划分树。
2) 查找——在划分树中查找某个子区间中第k大值。


604e3ff70446ba079c7ba5918b93385aa438f620

1.1.1 离线构建整个查询区间的划分树
在查询之前,我们先离线构建整个查询区间的划分树。建树过程比较简单,对于区间[l,r],首先通过对原数列排序找到这个区间的中间值的位置midmid=l+r2」,不大于中间值的数划入左子树[l,mid],大于中间值的数划入右子树[mid+1,r]。同时,对于第i个数,记录在[l,i]区间内有多少整数被划入左子树。然后继续对它的左子树区间[l,mid]和右子树区间[mid+1,r]递归建树,直至划分出最后一层的叶节点为止,显然,建树过程是自上而下的。
具体实现办法:
先将读入的数据排序成sorted[],取区间[l,r]的中间值sorted[mid]mid=l+r2」,然后扫描[l,r]区间,依次将每个整数划分到左子区间[l,mid]或右子区间[mid+1,r]中去。注意,被分到每个子树的整数是相对有序的,即对于被分到每一棵子树里面的数,不改变它们以前的相对顺序。另外,在进行这个过程的时候,记录一个类似前缀和的东西,即l到i这个区间内有多少整数被划分到左子树。设:
tree[p][i]——第p层中第i位置的整数值,初始序列为tree[0][]。
sorted[]——排序序列,即存储tree[0][]排序后的结果。
toleft[][]——toleft[p][i]表示第p层前i个数里中有多少个整数分入下一层的左子区间。
lpos和rpos——下一层左子区间和右子区间的指针。
same——当前区间等于中间值的整数个数。
下面给出实现建树的具体代码。

void build(int l,int r,int dep)           // 从dep层的区间[l,r]出发,自上而下构建划分树
{
if(l==r)return;// 若划分至叶子,则回溯
int mid=(l+r)>>1;// 计算区间的中间指针
int same=mid-l+1;// 计算[l,r]的中间值被分入下层后左子区间的
// 个数same
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++)// 搜索区间[l,r]中的每个数
{
if(tree[dep][i]<sorted[mid])// 若dep层的第i个数据比中间值小,则被划入
// 下一层的左子区间;若相同于中间值,被划入下一层的左子区间,中间值被分入下层后左子区间的个数-1;
// 若大于中间值,则被划入下一层的右子区间
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];
toleft[dep][i]=toleft[dep][l-1]+lpos-l;// 计算dep层的第1个数到第i个数放入下一层
// 左子区间的个数
}
build(l,mid,dep+1);// 递归计算下一层的左子区间
build(mid+1,r,dep+1);// 递归计算下一层的右子区间
}

1.1.2 在划分树上查询子区间[l,r]中第k大的数
如何在大区间[L,R]里查询子区间[l,r]中第k大的数呢(L≤l,r≤R)?我们从划分树的根出发,自上而下查找:
若查询至叶子(l==r),则该整数(tree[dep][l])为子区间[l,r]中第k大的数;否则区间[L,l-1]内有toleft[dep][l-1]个整数进入下一层的左子树,区间[L,r]内有toleft[dep][r]个整数进入下层的左子树。显然,在查询子区间[l,r]中有cnt=toleft[dep][r]-toleft[dep][l-1]个整数进入了下一层的左子树。如果cnt≥k,则递归查询左子树(对应区间[L,mid]);否则递归查询右子树(对应区间[mid+1,R])。
难点是,如何在对应子树的大区间中计算被查询的子区间[newl,newr]?
若递归查询左子树,则当前子区间的左边是上一层区间[L,l-1]里的toleft[dep][l-1]-toleft[dep][L-1]个整数,由此得到newl=L+toleft[dep][l-1]-toleft[dep][L-1];加上上一层查询区间[l,r]中的cnt个整数,newr=newl+cnt-1(这里-1是为了处理边界问题,值得大家认真思索),即在大区间[L,mid]里查询子区间[newl,newr]中第k大的值。
同理,若递归查询右子树,则[l,r]中有r-l-cnt个整数进入右子树,需要计算其中第k-cnt大的整数值。关键是如何计算被查询子区间的右指针newr:
当上一层的[l,r]和[r+1,R]中有若干个整数被分配至下一层左子区间,其中[r+1,R]中有toleft[dep][R]-toleft[dep][r]个整数位于左子区间右方(保持相对顺序不变),因此查询子区间的右指针移至r右方的第toleft[dep][R]-toleft[dep][r]个位置,即newr=r+toleft[dep][R]-toleft[dep][r]。显然,左指针newl=newr-(r-l-cnt)。
下面给出实现查询的具体代码。int query(int L,int R,int l,int r,int dep,int k)// `javascript
从划分树的dep层出发,自上而下在大区间
// [L,R]里查询子区间[l,r]中第k大的数
{
if(l==r)return tree[dep][l];// 若查询至叶子,则该整数为子区间[l,r]中
// 第k大的数
int mid=(L+R)>>1;// 取大区间的中间指针
int cnt=toleft[dep][r]-toleft[dep][l-1];// 计算[l,r]中被划入下一层左子区间的整数个数
if(cnt>=k)// 递归查询左子树,对应的大区间为[L,mid],
// 小区间为[newl,newr],计算其中第k大的值
int newl=L+toleft[dep][l-1]-toleft[dep][L-1];
int newr=newl+cnt-1;
return query(L,mid,newl,newr,dep+1,k);
}
Else// 递归查询右子树,对应的大区间为[mid+1,R],
// 小区间为[newl,newr],计算其中第k-cnt大的值
{
int newr=r+toleft[dep][R]-toleft[dep][r];
int newl=newr-(r-l-cnt);
return query(mid+1,R,newl,newr,dep+1,k-cnt);
}
}

**1.1.3 应用划分树解题**
虽然划分树是一种基于线段树的数据结构,但被分到同一子树的元素间的相对位置不改变,因此将其用于查询子区间[l,r]中第k大的值是十分适合的。
【1.1.1 K-th Number】
【问题描述】
您为Macrohard公司的数据结构部门工作,现在被要求编写一个新的数据结构,该数据结构能在一个数组段中快速地返回第k个次序统计数据。
也就是说,给出一个数组a[1..n],包含了不同的整数,程序要回答一系列这样形式的问题Q(i,j,k):“在数组a[i..j]段中第k个数是什么,如果这一段是排好序的?”
例如,数组a=(1,5,2,6,3,7,4),问题是Q(2,5,3),数组段a[2..5]是(5,2,6,3)。如果对这一段进行排序,得(2,3,5,6),第3个数是5,所以这个问题的答案是5。
输入:
输入的第一行给出数组的大小n和要回答的问题数m(1≤n≤100000,1≤m≤5000)。
第二行给出回答问题的数组,即n个不同绝对值不超过109的整数。
后面的m行给出问题描述,每个问题由3个整数组成:i、j和k(1≤i≤j≤n,1≤k≤j-i+1),表示相应的问题Q(i,j,k)。
输出:
对每个问题输出答案——在已排好序的a[i..j]段输出第k个数。

<div style="text-align: center">
 <img src="https://yqfile.alicdn.com/67f615c123eaaed1fa36b8a35af640ed05e19cb7.png " >
</div>
提示:本题海量输入,采用C风格输入-输出(scanf,printf),否则超时。
试题来源:ACM Northeastern Europe 2004,Northern Subregion
在线测试地址:POJ 2104
试题解析
简述题意:给出一个长度为n的整数序列,要求你反复采用快速查找方法查找某个子序列中第k大的值。
显然,采用划分树查询是最高效的。方法是:
1) 先离线构建整数序列的划分树(排序整数序列,调用过程build(1,n,0))。
2) 反复输入查询(a,b,c),通过调用函数query(1,n,a,b,0,c)计算和输出[a,b]区间中第c大的值。
程序清单

include

include

include

include

using namespace std;
const int MAXN=100010;// 整数序列规模大小的上限
int tree[30][MAXN];// tree[p][i]表示第p层中第i位置的值
int sorted[MAXN];// 已经排序的数
int toleft[30][MAXN];// toleft[p][i]表示第p层从1到i中有多少
// 个数被划入下一层的左子区间构建划分树的过程build(l,r,deep)和查询函数query(L,R,l,r,deep,k)如前所述,这里不再赘述。
下面,分别给出输入整型数的外挂函数和主程序。static inline int Rint()// Rint()为整型数输入函数。函数返回类型前
// 加上关键字inline即把Rint()指定为内联
{
struct X
{
int dig[256];// 标志有用码
X()
{
for(int i='0';i<='9';++i) dig[i]=1;
dig['-']=1;
}
};
static X fuck;
int s=1, v=0,c;// 假定正数,整数值初始化为0
for (; !fuck.dig[c=getchar()];);// 输入忽略串首的无用码
if (c=='-') s=0;// 设负数标志
else if (fuck.dig[c])v=c^48;// 记录最高位的数值
for(;fuck.dig[c=getchar()];v=v*10+(c^48));// 按照由高位至低位的顺序输入数码并计算整
// 数值v
return s ? v :-v;// 返回整数值
}

int main()// 主程序
{
int n,m;
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);// 计算排序数组sorted[]
build(1,n,0);// 从0层的根节点1出发,建立区间[1,n]的划分树
while(m--)// 依次和处理m个询问
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);// 输入当前询问
printf("%d\n", query(1,n,a,b,0,c));// 计算和输出[1,n]的子区间[a,b]中第c大的值
}
}
return 0;
}

在一些较复杂的综合题中,划分树经常被作为核心子程序,与其他算法配合使用。
【1.1.2 Super Mario】
【问题描述】
Mario是世界著名的水管工。他的“魁梧”体格和惊人的弹跳能力经常让我们想起他。现在可怜的公主又有麻烦了,Mario要去拯救他的情人。我们把到老板城堡路作为直线(其长度为n),在每个整数点i、高度hi的地方有一块砖。现在的问题是,如果Mario能跳的最大高度为h,在[L,R]区间内要有多少块砖,Mario才可以踩踏上去。
输入:
第一行给出整数T,表示测试用例的数目。
对每个测试用例:
第一行给出两个整数n、m(1≤n≤10^5,1≤m≤10^5),n是路的长度,m是查询次数。
下一行给出n个整数,表示每块砖的高度,范围是[0,1000000000]。
接下来的m行,每行给出3个整数L、R、h。(0≤L≤R<n,0≤h≤1000000000)。
输出:
对每个测试用例,输出“Case X:”(X是从1开始的测试用例的编号),然后给出m行,每行给出一个整数。第i个整数是针对第i个查询,Mario可以踩踏上去的砖块的个数。

<div style="text-align: center">
 <img src="https://yqfile.alicdn.com/8a05b1a4d51056ef5767d6eab00426f15874b967.png" >
</div>



试题来源:2012 ACM/ICPC Asia Regional Hangzhou Online
在线测试地址:HDOJ 4417
试题解析
简述题意:查询区间[L,R]内不大于H的数字个数,即在Mario最大跳跃高度为H的情况下,他在[L,R]内可踩踏多少块砖。
本题是一道综合题,采用的算法是二分查找+划分树:若Mario能够跳过高度为x的砖头,则所有高度不大于x的砖头都能够跳过。这就凸显出问题的单调性,使得二分查找方法得以施展。
我们将区间[s,t]映射成大小值区间=[l,r]=[1,(t-s)+1],每次计算中间指针mid=l+r2」,采用划分树计算区间[s,t]的中间值(即区间[s,t]中第mid大砖头的高度),并询问该值是否不大于Mario跳跃的最大高度h:若是,则说明Mario能够跳过的砖头数至少为mid,记下,并搜索右子区间[mid+1,t],尝试计算能跳过的更多砖头数;否则说明Mario不能够跳过mid块砖头,因此在左子区间[s,mid-1]中搜索能够跳过的砖头数。这个过程一直进行至区间不存在为止。此时记录下的砖头数即为问题的解。
程序清单

include

include

include

include

using namespace std;
const int MAXN=100010;         // 路长上限
int tree[30][MAXN];// tree[p][i]表示第p层中第i位置的值
int sorted[MAXN];// 已经排序的数
int toleft[30][MAXN];// toleft[p][i]表示第p层从1到i中有多少个数被划入
// 下一层的左子区间构建划分树的过程build(l,r,deep)和查询函数query(L,R,l,r,deep,k)如前所述,这里不再赘述。int solve(int n,int s,int t,int h)// Mario跳跃的最大高度为h时能够跳过区间[s,t]中的砖头数
{
int ans=0;// 能够跳过的砖头数初始时为0
int l=1;// 区间[s.t]映射成序号区间[l,r]
int r=(t-s)+1;
int mid;
while(l<=r)// 二分查找Mario能够跳过区间[s,t]中的砖头数
{
mid=(l+r)>>1;// 计算中间指针
int temp=query(1,n,s,t,0,mid);// 在区间[s,t]中查询第mid大的值
if(temp<=h)// 若该值不大于Mario能跳的最大高度h,则设定Mario能够
// 跳过区间[s,t]中的mid块砖头,继续搜索右子区间
{
ans=mid;
l=mid+1;
}
else r=mid-1;// 否则搜索左子区间
}
return ans;// 返回问题解
}

int main()
{
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(tree));
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++;// 区间以1为基准
t++;
printf("%d\n",solve(n,s,t,h));// 计算和输出Mario跳跃的最大高度为h时能够跳过区间
// [s,t]中的砖头数
}
}
return 0;
}

网友评论

登录后评论
0/500
评论
华章计算机
+ 关注