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

要解决这个问题，插入和删除可以用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