整体二分
最后更新于：2022年6月25日 下午
整体二分是 由 许昊然 于 2013 年集训队论文《浅谈数据结构题的几个非经典解法》提出的一类离线算法。
不修改版本
看了 OI-wiki 老半天，终于懂了，其它就是求一个区间 \([L, R]\) 中小于某个数的个数，可以转化成，求 \([1, R]\) 的答案减去 \([1, L - 1]\) 的答案，而最合适的数据结构就是 树状数组了。然后我们对原始区间的所有数分到两边去，为了保留原始的位置，我们存一下位置和值。那么大于估计答案 m 的值放在右边，否则放在左边。注意到右边所有的数都是大于 m 的。因此我们就需要看一下这个区间里有多少个值放在了左边，我们需要把它减掉！就是这样结束了。
模板例题：https://www.luogu.com.cn/problem/P3834 的提交
注意到我们可以把 \(a\) 中数组的添加操作，当作修改操作！这样就通了！
单点更新版本
例题：https://www.luogu.com.cn/problem/P2617 的提交 比用真在线不离散化动态开点的做法要快不少
用
k = -1表示修改，可以节省内存，且更加优雅
区间更新版本
https://www.luogu.com.cn/problem/P3332 求第 k 大，我们把所有的数取负数就是求第 k 小了 0.0。机智如我！另外我们可以用区间修改的树状数组替代线段树，nice，提交
这题如果强制在线，可以线段树套权值线段树也可以做就是写的比较恶心人
拓展应用
待补