简介
莫队是一种离线求区间信息的算法，可以做到 \(O((N+Q) \cdot\sqrt{N})\)。莫队中使用了分块的思想。
首先考虑一个问题：给定一个长度为 \(N\) 序列 \(A\) 和 \(Q\) 次询问，每次询问查询区间 \([X_i,Y_i]\) 的和。（请先忘掉前缀和、线段树、树状数组什么的）
比如以下数据：
5 4
3 2 2 1 5
1 3
4 5
2 6
1 1
2 2
莫队的思想是：记录一个 \(l,r\) 和 \(sum\)，其中 \(sum=\sum \limits_{i=l}^r A_i\)。每次求一个新区间时，不断移动 \(l,r\)，并维护 \(sum\)。
如：
int l = 1, r = 0, sum = 0, x, y;cin >> x >> y;
for(; l > x; sum += a[--l]) {
}
for(; r < y; sum += a[++r]) {
}
for(; l < x; sum -= a[l++]) {
}
for(; r > y; sum -= a[r--]) {
}
cout << sum << "\n";
可这样仍然是 \(O(N)\) 的。
所以，我们可以离线求解。我们可以对查询区间按某种方式排序，使得时间复杂度更优。而莫队的排序策略是这样的：
- 如果 \(\lfloor \frac{X_i}{\sqrt N} \rfloor = \lfloor \frac{X_j}{\sqrt N} \rfloor\)：
- 如果 \(Y_i < Y_j\)，那么排序后 \(i\) 放在 \(j\) 前面。
- 否则排序后 \(j\) 放在 \(i\) 前面。
- 如果 \(\lfloor \frac{X_i}{\sqrt N} \rfloor \ne \lfloor \frac{X_j}{\sqrt N} \rfloor\)：
- 如果 \(\lfloor \frac{X_i}{\sqrt N} \rfloor <\lfloor \frac{X_j}{\sqrt N} \rfloor\)，那么排序后 \(i\) 放在 \(j\) 前面。
- 否则排序后 \(j\) 放在 \(i\) 前面。
按照这样的方式排序，那么 \(l\) 在一个块中会移动 \(O(Q)\) 次，共移动 \(O(Q\cdot\sqrt N)\)
次，右端点在同一个块中都是递增的，所以在一个块中移动 \(O(N)\) 次，共移动 \(O(N \cdot
\sqrt N)\) 次。总时间复杂度 \(O((N+Q) \cdot \sqrt N)\)。
莫队不仅能求解区间和，很多其他区间信息也能求解。
优化
可以发现，每次处理完一个块后，右端点都要从新移动回去，所以我们可以让所有偶数块右端点从小到大，奇数块从大到小，可以优化大约 \(\frac{1}{2}\) 的常数。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MAXN = 200001, MAXS = 447, MAXQ = 200001;struct Node {int l, r, id;
}s[MAXQ];int n, q, a[MAXN];
ll sum, ans[MAXQ];int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> q;for(int i = 1; i <= n; ++i) {cin >> a[i];}for(int i = 1; i <= q; ++i) {cin >> s[i].l >> s[i].r;s[i].id = i;}sort(s + 1, s + q + 1, [](const Node &a, const Node &b) { return (a.l / MAXS == b.l / MAXS ? (a.l / MAXS % 2 ? a.r > b.r : a.r < b.r) : a.l / MAXS < b.l / MAXS); });ll sum = 0;for(int i = 1, x = 1, y = 0; i <= q; ++i) {for(; x > s[i].l; sum += a[--x]) {}for(; y < s[i].r; sum += a[++y]) {}for(; x < s[i].l; sum -= a[x++]) {}for(; y > s[i].r; sum -= a[y--]) {}ans[s[i].id] = sum;}for(int i = 1; i <= q; ++i) {cout << ans[i] << "\n";}return 0;
}
