→ FRAXIS: 可不可以简单介绍一下莫队算法的功用啊？ 02/05 01:26
现在有许多个区间查询 Q = { [a1,b1] , [a2,b2] , ... , [ak,bk] }
预计其查询结果是 r[a1,b1] ... r[ak,bk]
假设问题具备此性质：
已知 r[a,b] ，可以快速求得边界差一的结果如 r[a-1,b] r[a+1,b] r[a,b-1] r[a,b+1]
令计算时间为 O(f(n))
那么，已知 r[ai,bi] 推得 r[aj,bj] 的时间就是 O((|ai-aj| + |bi-bj|) * f(n))
即 rectangular distance (L1)
我们现在替 Q 中所有查询，安排适当计算顺序，让总时间最少。
查询视为座标，即 minimum spanning tree with rectangular distance O(k log k)
找到树之后，跑个DFS或BFS，就得到最佳的计算顺序。
(理论上 steiner tree 效果更好，不过它是 NP-hard ...)
我理解的莫队算法是这样。
至于为什么莫队算法宣称 O(n^1.5) ，我还没搞清楚...