[蓝桥杯学习] 树状数组的二分

发布时间:2024年01月06日

要解决这个问题,插入和删除可以用STL实现,2操作如果用树状数组实现的话,将数的值作为树状数组的下标,即值域。

树状数组有两种操作,一个是更新某点的值,另一个是求区间和。

mid = (l+r)/2 ,求和 t[a+1] 到 t[mid] ,设为x,如果x小于k,就mid右移,如果x大于k,就mid左移

二分查找的代码

注意:不同点是,可能第k大的数 c 到第 k+1 大的数 b之间都是到a求和有k个值,所以我们要找左边界,不断更新ans,遇到相等的,先记录下来,然后把mid左移。

int find(int a,int k)
{
  int l = a+1; 
  int r = maxn;
  int mid;
  int ans=-1;
  while(l <= r)
  {
    mid = (l+r) >> 1;
    if(query(mid) - query(a) = k) ans = mid;
    if(query(mid) - query(a) >= k) r = mid-1;
    else l = mid+1; 
  }
  return ans;
}

例题

第i个小朋友前面有ai个小朋友,如果后面没有比他低的,那么他的身高是 ai+1

如果我们从前往后遍历数组a[i] ,我们是无法知道后面小朋友的身高,所以要从后往前遍历,但是,计算中间小朋友的身高时,还是得知道后面有多少人比他低。

使用树状数组时,从后往前遍历时,每确定一个身高,就把该下标从1变为0,这样,往前计算小朋友身高时,通过求和,就能得到这个小朋友的身高,例:原本是111111,两次删除之后是100111,ai=3的小朋友,ai+1=4,但是很明显,确定身高的小朋友都比他低,所以要后移两位(通过0的存在实现了),移到了6

文章来源:https://blog.csdn.net/weixin_73512213/article/details/135428610
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。