中山网站推广词,佛山网站建设3lue,用php做的订票网站,wordpress备份数库要解决这个问题#xff0c;插入和删除可以用STL实现#xff0c;2操作如果用树状数组实现的话#xff0c;将数的值作为树状数组的下标#xff0c;即值域。
树状数组有两种操作#xff0c;一个是更新某点的值#xff0c;另一个是求区间和。 mid (lr)/2 #xff0c;求和 …
要解决这个问题插入和删除可以用STL实现2操作如果用树状数组实现的话将数的值作为树状数组的下标即值域。
树状数组有两种操作一个是更新某点的值另一个是求区间和。 mid (lr)/2 求和 t[a1] 到 t[mid] 设为x如果x小于k就mid右移如果x大于k就mid左移 二分查找的代码
注意不同点是可能第k大的数 c 到第 k1 大的数 b之间都是到a求和有k个值所以我们要找左边界不断更新ans遇到相等的先记录下来然后把mid左移。
int find(int a,int k)
{int l a1; int r maxn;int mid;int ans-1;while(l r){mid (lr) 1;if(query(mid) - query(a) k) ans mid;if(query(mid) - query(a) k) r mid-1;else l mid1; }return ans;
} 例题 第i个小朋友前面有ai个小朋友如果后面没有比他低的那么他的身高是 ai1
如果我们从前往后遍历数组a[i] 我们是无法知道后面小朋友的身高所以要从后往前遍历但是计算中间小朋友的身高时还是得知道后面有多少人比他低。
使用树状数组时从后往前遍历时每确定一个身高就把该下标从1变为0这样往前计算小朋友身高时通过求和就能得到这个小朋友的身高例原本是111111两次删除之后是100111ai3的小朋友ai14但是很明显确定身高的小朋友都比他低所以要后移两位通过0的存在实现了移到了6
