普通莫队由莫涛总结并实现。可以在 \(\mathcal{O(n\sqrt{n})}\) 的时间复杂度内解决不带修的区间问题。
那什么样的题才能用莫队呢？
最重要的特征是知道区间 \([l,r]\) 的答案，可以 \(\mathcal{O(1)}\) 得知 \([l-1,r]\)，\([l,r-1]\)，\([l+1,r]\)，\([l,r+1]\) 区间的答案。
先来看一个例子：
给出序列 \(\{a_n\}\)，\(m\) 次询问，每次求区间 \([l_i,r_i]\) 的和。
这道题固然可以用前缀和写，但这里只讨论莫队：