莫队算法：对于两个区间的查询[l1,r1] ,[l2,r2]如果每增加一个区间元素或者删除，都能做到O(1)的话那么从[l1,r1]转移到[l2,r2]，暴力可以做到|l1-l2|+|r1-r2|，就是manhattan距离莫队的论文一直没有找到，所以只是大致的了解下，应该是证明出构造出哈密尔顿路径是最优的。但是可以用manhattan mst来构造，大约会是两倍，然后莫队证明出这样转移的上限是O(n*sqrt(n))。所以对于这种无修改的区间查询来说可以先将所有的区间，看成二维平面上的点，求一次manhattan mst，然后根据mst来进行转移相邻的两个区间的查询转移，暴力解决。
Via http://blog.csdn.net/huzecong/article/details/8576908
http://blog.csdn.net/acm_cxlove/article/details/8894431
在此感谢
据说这个算法是莫涛提出的（Orz！），但是在网上到处都搜不到相关资料，最后问pty才知道的。这个算法是用于处理一类不带修改的区间查询问题的离线算法，其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。比如下面这个例题（清橙A1206《小Z的袜子》，就是莫队出的题）：
给定一个长为N的序列，每个元素的值是其颜色。有M次询问，每次询问从一个区间中随机选取两个元素同色的概率。
一次询问[l,r]的答案即，其中是区间中第i中颜色的个数。显然暴力是O(NM)的，而且一般的区间问题的思路似乎不适用。
我们先考虑一个简化的问题：所有的查询区间的左端点都是1。那么我们可以按右端点排序，假设已经处理出了[1,r]的答案，考虑转移到[1,r+k]，即添加k个元素，这个可以在O(k)的复杂度内求出。那么处理所有区间的复杂度（不考虑排序）就是O(N)。
那么如果是从[l,r]转移到[l’,r’]呢？复杂度即O(|r’-r|+|l’-l|)，也即点(l,r)到点(l’,r’)的曼哈顿距离。那么如果将所有询问转化成二维平面中的点，求曼哈顿距离最小生成树，再按照生成树的顺序做，就可以最小化区间之间转移的复杂度。可以证明（我不会证……似乎莫队的论文里有），这样做的复杂度是O(N1.5)的。问题也就得到了解决。
[Dr.Lib]Note:Algorithm – 莫队算法 by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.