从第K元素看数据结构

声明:本文涉及的源代码及文章请点击这里下载,本文版权归IronOxide所有。博客地址:http://www.cppblog.com/IronOxide/
这篇文章讨论的是序列中第
K大或第K小元素,由于第K大元素可以转化为求第N-K+1小元素(N为序列的长度),所以,本文专注于讨论第K小元素。

本文讨论的几个问题:

1. 对给定整数序列,求该序列中第K小的元素。

2. 对某一整数序列,允许动态更改序列中的数。动态查询序列中第K小元素。

3. 给定一个整数序列和若干个区间,回答该区间内第K小元素。

4. 对某一整数序列,允许动态更改序列中的数。动态查询序列中的第K小元素。

【关键字】

K小元素 树状数组 线段树 平衡二叉树 归并树 划分树 单调队列 块状表

【问题一】

问题描述

给出一个乱序整数序列a[1…n] ,求该序列中的第K小元素。(1<=K<=N)。

算法分析

用基于快速排序的分治算法,期望复杂度为O(N)

代码

int qs(int *a , int l , int r , int k){
     
if(l == r)  return a[l] ;
     
int i = l , j = r , x = a[(l+r)>>1] , temp ; 
     
do{
         
while(a[i] < x) ++ i ; 
         
while(a[j] > x) -- j ; 
         
if(i <= j){
             temp 
= a[i] ;  a[i] = a[j] ,  a[j] = temp ;  
             i
++ ;  j-- ; 
         }
     }
while(i<=j) ;
     
if(k <= j)  return qs(a , l , j , k);
     
if(k >= i)  return qs(a , i , r , k);
     
return x ;
}

 

练习

RQNOJ 350 这题数据量比较小1≤N≤10000,1≤M≤2000 。所以计算量不会超过10^7。当然用到后面的归并树或划分树,能将复杂度降低。

 

【问题二】

问题描述

给出一个乱序整数序列a[1...n] ,有3种操作:

操作一:ADD NUM 往序列添加一个数NUM
    操作二:DEL NUM 从序列中删除一个数NUM(若有多个,只删除一个)。

操作三:QUERY K 询问当前序列中第K小的数。

输出每次询问的数。假设操作的次数为M

算法分析:

这题实际上就是一边动态增删点,一边查询第K小数。这类题有两种思维方法:一是二分答案,对当前测试值mid,查询mid在当前序列中的排名rank 然后根据rank决定向左边还是右边继续二分。另一种是直接求第K小元素。

这个题可以用各种类型的数据结构解决,其时间复杂度和编程复杂度稍有区别:

线段树:运用第一种思维,当添加(删除)一个数x时,相当于往线段树上添加(删除)一条(x , maxlen)(注意是闭区间)长度的线段。这样询问时,覆盖[mid , mid]区间的线段数就是比mid小的数,加上1就是rank。二分次数为log(maxlen) ,查一次midrank 复杂度为O(logN) 。所以总复杂度上界为O(M*logN*logN) 。为方便比较,这里认为log(maxlen)等于logN

树状数组:

第一种思维:这个相对简单,因为树状数组求比mid小的数就一个getsum(mid-1)就搞定。

复杂度同线段树一样。只是常数很小,代码量也很小。

第二种思维:我只能说很巧妙。回顾树状数组求和时的操作:

代码

int getsum(int x ){
     
int res = 0 ;
     
for( ; x>0 ; x-=lowbit(x) )  res += arr[x] ;
     
return res ;  
   }


对二进制数10100010 是依次累加arr[10100010] , arr[10100000] , arr[10000000] 。从而得到小于x的数的个数。当反过来看的时候,就有了这种方法:从高位到低位依次确定答案的当前为是0还是1,首先假设是1,判断累计结果是否会超过K,超过K则假设不成立,应为0,否则继续确定下一位。看程序就明白了。

代码

int getkth(int k){
           
int ans = 0 , cnt = 0 , i ;
           
for(i = 20 ; i>=0 ; --i){
                 ans 
+= 1<<i ;
                 
if(ans>=maxn||cnt+c[ans]>=k) ans-=1<<i ;
                 
else cnt +=c[ans] ;      
           }
           
return ans+1 ; 
      }


复杂度:自然就比第一种少了一个阶。O(M*logN)

平衡二叉树:

各种平衡二叉树都可以解决这个问题:Size Balance Tree Spaly Treap ,红黑树等等。 不得不说,Size Balance Tree解这个问题是比较方便的。因为SBT本身就有一个Select操作,直接调用一下,就出来了。

代码

复杂度:用的是第二种思维。O(M*logN)

总结:

其实,综合起来,各种数据结构,各种算法 ,各种纠结。平衡树太复杂,线段树又高了点(一般情况不会有问题的)。最好的方法还是树状数组的二进制算法,时间复杂度和编程复杂度达到双赢。

但是,总结起来,发现线段树或者树状数组所消耗的空间跟数据的范围有关,当序列元素是浮点数或者范围很大时,就有点力不从心了(当然,离线的情况可以离散化,在线的某些情况可以离散化),而用平衡二叉树就不存在这样的问题。原来平衡二叉树才是王道

练习:

最近发现,基于这种思想的题目还真是不少啊~ ~ POJ Double Queue

[NOI2004]郁闷的出纳员 工资反过来看,职员工资不变,而是工资下界在变而已。当降低工资下界时,为了知道哪些职员走人了,我还用了个二叉堆。。。。。

POJ 2761 Feed the dogs 首先该题用接下来问题3的一个特例。但其特殊性在于任意两个区间不包含,导致把区间按左端点(不会存在相同左端点滴,否则必包含)排序之后,依次扫描每个区间,当前区间和前一个区间相交的部分不动,前一区间有而当前区间没有的部分删除,前一区间没有而当前区间有的部分添加。这能保证每个元素正好添删各一次。

POJ 2823 Sliding Window 太特殊了,最大值就是第K 最小值就是第1小(这是一个很重要的启示:树状数组也可以动态求最值)。单调队列可以弄成线性算法。

HUNNU 10571 Counting Girls 第四届华中南邀请赛 但数据与题目稍有不符 但可以确定每个数大于等于0且不超过200000 。关键是求第X th 到第 Y th MMrating 和要注意下。

KiKi's K-Number 这题就没什么好说的了。求[a+1,MaxnInt]的第K 小的数,先求出[0,a]有多少个数,设为cnt,只要求第K+cnt小的数就可以了。哦,题目说是求第K大的,实际是求第K小的,这有点意思~

 

【问题三】

问题描述

给定一个序列a[1...n] m 个询问 每次询问a[i...j]之间第K小的数。

(引用一句英文:You can assume that n<100001 and m<50001

算法分析

块状表

如果这道题能够想到用块状表的话,思维复杂度和编程复杂度都不高~,考虑这样操作:

首先预处理,将序列划分成sqrt(N)个小段,每段长[sqrt(N)] ,划分时,将每小段排好序。

然后就是查询了,对区间[i,j]的查询,同样采用二分求比测试值mid小的个数。ij所在的零散的两小段直接枚举求,中间完整的小段则二分查找求。
这样一次查询时间复杂度为


于是总复杂度为:


当然,这里计算量是比较大的,实际写了个程序也是超时的。但当
M比较小时,也未尝不是一种好的选择(或者当开阔思路吧,但对问题四却正好打个擦边球)。

 

划分树

划分树应该是解决这道题复杂度最低的方法,复杂度为

思想其实很简答,用线段树把整个序列分成若干区间。建树时,对区间[l,r]划分:选择该区间的中位数value(注意:可以先用快速排序对原来序列排个序,于是可以速度得到中位数),将小于等于value的不超过mid-l+1个数划分到[l,mid]区间,其余划分到[mid+1,r]区间,用一个数组把每层划分后的序列保存起来。

然后,查找的时候,Find(x , l , r , k)表示超找x节点内区间[l,r]K小的数。将该节点区间分成三个区间[seg_left , l-1] [l , r ] , [r+1 , seg_right]来讨论问题,他们在划分过程中分到[l,mid]区间的个数依次为ls , ms , rs 。若ms<=K自然查左边区间, Find(2*x , l+ls , l+ls+ms-1,K)。否则自然查右边,计算下标很烦啊。有代码在~

代码

void build(lld d ,lld l , lld r ){
     
if(l == r)  return  ;
     lld i , mid 
= (l+r)>>1 , j=l , k=mid+1  ;
     
for(i = l ; i <= r ; ++ i){
           s[d][i] 
= s[d][i-1] ; 
           
if(tr[d][i] <= mid){
               s[d][i]
++ ;  
               tr[d
+1][j++= tr[d][i]; 
           }
else{
               tr[d
+1][k++= tr[d][i];
           }
     }
     build(d
+1 ,l , mid);
     build(d
+1 , mid+1 , r);
}

lld getkth(lld d ,lld lp ,lld rp , lld l , lld r , lld k){
    
if(lp == rp )  return tr[d][lp] ;
    lld mid 
= (lp + rp)>>1 ; 
    
if(k<=s[d][r]-s[d][l-1])
        
return getkth(d+1 ,lp , mid , 
                         lp
+s[d][l-1]-s[d][lp-1] , lp+s[d][r]-s[d][lp-1]-1 , k );
    
else 
        
return getkth(d+1 ,mid+1 , rp , mid+1+(l-lp)-(s[d][l-1]-s[d][lp-1]) , 
                        mid
+(r-lp+1)-(s[d][r]-s[d][lp-1]) , k-(s[d][r]-s[d][l-1]) );
}


归并树

归并树思想就跟简单了,说白了就是线段树每个区间[l,r]内的数都排好序然后保存起来, 从两个儿子到父亲节点,其实就是两个有序序列归并成一个有序序列,所以就称归并树了。

用前面说的二分答案,对测试值midrank。查找的时候,将查找区间划分成线段树中若干子区间之并,很明显各个子区间小于mid的个数加起来,就是该区间小于mid的个数。而每个子区间又是有序的,所有二分可以很快找到小区间小于mid的个数。

总结起来,有三次二分:

1.二分答案;

2.查找区间[a,b]划分成不超过log(b - a)个小区间;

3.对每个子区间,二分查找小于mid的个数;

于是,整个算法复杂度为:

总结

对本问题,提供了三种算法,其中基于快排的划分算法是最快的;块状表思维和编程都比较简单,但是复杂度比较高;归并树算法思想很好,二分答案,求rank 后面问题四的算法就是根据这种思维设计出来的。

练习

POJ 2761 Feed the dogs

POJ 2104 K-th Number

NOI 2010 超级刚琴 这题还真有点难度。

思路:划分树++单调队列

对每个区间,起点为i+1,终点在区间[i+L,i+R]。计s[i]=a[0]+a[1]+...+a[i] (规定a[0]=0), opt[i,k]表示第k大的s[j] (i+L<=j<=i+R),即opt[i,k] = Max_k { s[j] | i+L<=j<=i+R} Max_k表示第k大)。

先进行两个预处理工作:

1.s[1] , s[2] , s[3] , .. s[n] 建成一颗静态划分树。

2.用单调队列预处理出所有opt[i,1]的值,并将所有opt[i,1]-s[i]用一个堆维护起来。当然也可以直接通过查询[i+L,i+R]区间第1大的值来预处理opt[i,1]

下面开始取值,并更新:依次从堆中取出最大值,设是opt[i,j]-s[i],把它累加至答案,再查询划分树中[i+L , i+R]区间第j+1大的值opt[i,j+1] , opt[i,j+1]-s[i]后入堆。直到累加次数为K停止。

 

问题四

问题描述

给定一个原始序列a[1...n] , 有两种操作:

操作一: QUERY i j k 询问当前序列中,a[i...j]之间第k小的数是多少

操作二: CHANG I T a[i]改为T

输出每次询问的结果。N<=50000 , 操作次数M<=10000

算法分析

块状表

a[1...n]分成sqrt(N)段,每段长[sqrt(N)],为方便二分查找每段,将每段排好序,对操作二,先删去a[i] , 在插入T , 维护该块得有序性,复杂度为O(sqrt(N))

对操作一,二分答案,设当前测试值为mid , 先统计两端零散块,O(2*sqrt(N)) 。对中间完整块,每块二分查找,总复杂度为:

线段树+平衡二叉树

 

序列被线段树划分为区间节点,而每个节点又是一颗平衡二叉树,平衡二叉树放的是该区间段的所有数。

对操作二,依次更新从跟区间到叶子节点区间的平衡树即可(先删除a[i],在插入T),考虑复杂度,第一层规模为N,第二层规模为N/2,第k层规模为 N/2^k 。进行依次操作二的复杂度为:
    
    这里 K = [logN]
对操作一:询问区间被划分为不超过[logN]个线段树节点之并,每次区间查找上界为logN 。所以,对每个测试值mid , 耗时(logN)^2 , 故查询一次的复杂度为:
   

总复杂度为 
      

练习

ZOJ 2112 Dynamic Rankings

posted on 2012-08-29 21:16 IronOxide 阅读(1242) 评论(0)  编辑 收藏 引用 所属分类: 算法竞赛


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔分类

随笔档案

ACMer

方向

搜索

最新评论

阅读排行榜

评论排行榜