这里先写如何证明普通整体二分的复杂度是 \(O(n\log n\log V)\) 的:
标签:二分,frac,log,sum,整体,aligned,复杂度 From: https://www.cnblogs.com/fzrcy/p/18028086考虑如何将复杂度卡到这个上限。显然要使得每个询问的答案均匀的分布在值域 \([1,V]\) 中,也就是在每次值域分半时,操作数(询问和修改)也分半,即:
\[\begin{aligned} T(n,V)&=\\ &=2T(\frac{n}{2},\frac{V}{2})+n\log n\\ &=\sum_{i}2^i\frac{n}{2^i}\log\frac{n}{2^i}\\ &=\sum_{i}n(\log n-i)\\ &=n\log n\log V -n\frac{\log V(\log V+1)}{2} \end{aligned} \]我们将最后一项忽略就得到了整体二分的复杂度是 \(O(n\log n\log V)\)。