整除分块套整除分块
也就是求：
\[O\left(\sum_{i=1}^{\sqrt n}\sqrt{\frac{n}{i}}\right) \]设 \(f(n)=\sum\limits_{i=1}^{n}\dfrac{1}{\sqrt{i}}\)，那么原式就是 \(O(\sqrt n\times f(\sqrt n))\)，因此我们只需要求 \(f(n)\) 即可。
把 \(f(n)\) 从求和式改写为积分式，也就是：
\[f(n)=\int_{1}^n \frac{1}{\sqrt x} dx \]容易得到 \(f(n)=O(\sqrt n)\)，故原式等于 \(O(n^{\frac{3}{4}})\)。
杜教筛
如果用线性筛预处理前 \(B\) 个，那么杜教筛的复杂度可以被表示为：
\[O(B+\sum_{i=1}^{n/ B}\sqrt{\frac{n}{i}}) \]类似的，原式可以被表示为 \(O(B+\sqrt n\times \sqrt \frac{n}{B})=O(B+\frac{n}{\sqrt B})\)，用均值不等式可以得出其最优复杂度在 \(B=n^{\frac{2}{3}}\) 时取到，为 \(O(n^{\frac{2}{3}})\)。
树剖复杂度
- 为什么树剖的复杂度是 \(O(\log n)\) 的？
容易发现，树剖的复杂度等于两点之间的重链数，而两点之间的重链数又于两点之间的虚边数同阶。
由于树剖每次都选取最大的子节点作为重儿子，因此若一个点经过虚边到达父节点，那么子树大小一定至少 \(\times 2\)。
考虑反证法，如果没有至少 \(\times 2\)，那么这就意味这自己的子树大小与父节点子树大小的比值大于 \(\dfrac{1}{2}\)，那么自己就一定是父节点的重儿子（不可能有两个节点的子树大小都大于父节点的 \(\dfrac{1}{2}\)），与自己是轻儿子的事实相反。
翻倍的次数最多 \(O(\log n)\) 次，因此虚边数是 \(O(\log n)\) 的，故树剖的复杂度是 \(O(\log n)\)。
点分治的复杂度证明类似。
调和级数套快速幂
也就是求：
\[O\left(\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\log \frac{n}{ij}\right) \]设 \(f(n)=\sum\limits_{i=1}^n\log\dfrac{n}{i}\)，那么原式就是 \(\sum\limits_{i=1}^n f(\dfrac{n}{i})\)，我们先求 \(f(n)\)。
构造方程 \(\log \dfrac{n}{x} = y\)，解得 \(x=\dfrac{n}{2^y}\)，也就是说，在 \(1\sim n\) 的 \(\log \dfrac{n}{i}\) 中，比 \(x\) 大的有 \(\dfrac{n}{2^x}\) 个，那么等于 \(x\) 的就有 \(\dfrac{n}{2^{x-1}}-\dfrac{n}{2^x}=\dfrac{n}{2^{x-1}}\) 个，因此，我们可以将 \(f\) 转化为个数累加式（就是所有的值乘上这个值出现的次数）：
\[f(n)=\sum_{i=1}^n\log\frac{n}{i}=\sum_{i=1}^{\infty}i\times \frac{n}{2^{i-1}}=O(n \sum_{i=1}^{\infty}\frac{i}{2^i}) \]后半部分是一个等差数列乘等比数列的无限项和，用错位相减法容易得到其值为常数 \(2\)，因此 \(f(n)=O(n)\)。
那么原式就等于 \(O(\sum\limits_{i=1}^n\dfrac{n}{i})=O(n\log n)\)。
标签：frac,log,dfrac,复杂度,sqrt,经典,sum From： https://www.cnblogs.com/TKXZ133/p/17757584.html