我研究了一下，如果元素有 n 个，查询有 m 个，当 m 至少为 n^0.5， 莫队算法那空间复杂度应该会是 O((n+m) * n^0.5 * (状态转移cost) + 排序) 空间是 O(m+状态表示)。 所以我猜主要的优势是在好实作和省空间吧。 我尝试了几个题目（假设m = O(n)） 1. Range inversion counting: 求区间内的逆序对 2. Range sum of distinct elements: 区间内相异元素之和 3. Range second frequency moment: 求区间内元素出现次数的平方和 4. Range mode query: 求区间内的众数 1 的 offline 查询为 O(n^0.5 lg n) online 查询为 O(n^0.5) 空间 O(n^1.5) 或查询为 O(n^0.5 lg n) 空间 O(n) 2, 3, 4 的 offline 查询为 O(n^0.5) 4 的 online 查询为 O(n^0.5) 空间 O(n) 2, 3 的 online 查询为 O(n^0.5) 空间 O(n^1.5) 或查询为 O(n^0.5 lg n) 空间 O(n) 不知道能不能做成 查询为 O(n^0.5) 空间 O(n) 至於动态的话，就把 block 大小调小一点就可以了。 好像还有看到题目是 range distinct elements，找区间相异数字的个数， 这应该是O(lg n)可解的。 还有一些相关的问题，像是区间 majority，区间 minority， 区间前 k 大 (sorted/unsorted)，或是区间出现最多次的 k 个元素。 -- 这技巧蛮有趣的，不知道还有没有其他神奇的技巧呢？ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1423324040.A.C3E.html ※ 编辑: FRAXIS (129.170.195.149), 02/09/2015 23:24:59