Open Kewth opened 5 years ago
https://kewth.github.io/2019/10/16/%E8%8E%AB%E9%98%9F%E4%BA%8C%E6%AC%A1%E7%A6%BB%E7%BA%BF/#more
莫队算法可以通过单点增量的方式以 $O(n\sqrt{n}K)$ （认为 $n, q$ 同阶）的复杂度离线处理若干区间信息询问。其中每次单点增量，即每次端点移动的复杂度为 $O(K)$ 。大多数情况下端点移动的复杂度是 $O(1)$ 的，这样的问题一般是统计区间内的“数”。而统计区间内的“数对”这样的问题往往难以 $O(1)$ 处理端点移动。
https://kewth.github.io/2019/10/16/%E8%8E%AB%E9%98%9F%E4%BA%8C%E6%AC%A1%E7%A6%BB%E7%BA%BF/#more
莫队算法可以通过单点增量的方式以 $O(n\sqrt{n}K)$ （认为 $n, q$ 同阶）的复杂度离线处理若干区间信息询问。其中每次单点增量，即每次端点移动的复杂度为 $O(K)$ 。大多数情况下端点移动的复杂度是 $O(1)$ 的，这样的问题一般是统计区间内的“数”。而统计区间内的“数对”这样的问题往往难以 $O(1)$ 处理端点移动。