Standard Mo's Algorithm

Form

Assume \(n=m\), then for interval query problems on a sequence, if the answer for \([l,r]\) can be extended to the answers for \([l-1,r],[l+1,r],[l,r+1],[l,r-1]\) (i.e., intervals adjacent to \([l,r]\)) in \(O(1)\) time, then all queries can be answered in \(O(n\sqrt{n})\) complexity.

Explanation

After offline processing and sorting, handle each query in order, and brute-force transfer the answer from the previous interval to the next interval (by moving step by step).

Sorting Method

For interval \([l,r]\), sort in ascending order with the block number of \(l\) as the first key and \(r\) as the second key.

Implementation

void move(int pos, int sign) {
  // update nowAns
}

void solve() {
  BLOCK_SIZE = int(ceil(pow(n, 0.5)));
  sort(querys, querys + m);
  for (int i = 0; i < m; ++i) {
    const query &q = querys[i];
    while (l > q.l) move(--l, 1);
    while (r < q.r) move(++r, 1);
    while (l < q.l) move(l++, -1);
    while (r > q.r) move(r--, -1);
    ans[q.id] = nowAns;
  }
}

Complexity Analysis

The following discussion assumes \(n\) and \(m\) are of the same order.

First, the blocking step: its time complexity is \(O(\sqrt{n}\cdot\sqrt{n}\log\sqrt{n}+n\log n)=O(n\log n)\).

Next comes the essence of Mo's algorithm. Below we prove its time complexity is \(O(n\sqrt{n})\) using a simple middle school method.

Proof

Proof: Let the maximum \(L\) in each block be \(\max_1,\max_2,\max_3, \cdots , \max_{\lceil\sqrt{n}\rceil}\).

From the first sorting, we know \(\max_1 \le \max_2 \le \cdots \le \max_{\lceil\sqrt{n}\rceil}\).

Obviously, brute-forcing the first query in each block takes \(O(n)\) time.

Consider the worst case: in each block, the maximum \(R\) is \(n\), and each modification operation requires changing \(L\) from \(\max_{i - 1}\) to \(\max_i\) or from \(\max_i\) to \(\max_{i - 1}\).

Consider \(R\): Since \(R\) is already sorted within a block, modifying it within the same block takes \(O(n)\) time. For all blocks, this is \(O(n\sqrt{n})\).

Focus on \(L\): Since each change takes \(O(\max_i-\max_{i-1})\) time, the time complexity within the same block is \(O(\sqrt{n}\cdot(\max_i-\max_{i-1}))\).

Combining the time complexity of \(L\) for all blocks, we get:

The total time complexity for \(L\) is

\[ \begin{aligned} & O(\sqrt{n}(\max{}_1-1)+\sqrt{n}(\max{}_2-\max{}_1)+\sqrt{n}(\max{}_3-\max{}_2)+\cdots+\sqrt{n}(\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1))} \\ = \phantom{} & O(\sqrt{n}\cdot(\max{}_1-1+\max{}_2-\max{}_1+\max{}_3-\max{}_2+\cdots+\max{}_{\lceil\sqrt{n}\rceil-1}-\max{}_{\lceil\sqrt{n}\rceil-2}+\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1)}) \\ = \phantom{} & O(\sqrt{n}\cdot(\max{}_{\lceil\sqrt{n}\rceil}-1))\\ \end{aligned} \]

(telescoping sum)

From the problem, \(\max_{\lceil\sqrt{n}\rceil}\) is at most \(n\), so the worst-case total time complexity for \(L\) is \(O(n\sqrt{n})\).

In summary, the time complexity of Mo's algorithm is \(O(n\sqrt{n})\).

However, for other values of \(m\), such as \(m<n\), the blocking method needs to be changed to become more optimal.

How to block?

Let the block length be \(S\). Then for any queries within the same block, the moving distance is \(n\), there are \(\displaystyle \frac{n}{S}\) blocks in total, so the total number of moves is \(\displaystyle \frac{n^2}{S}\). Moves may cross blocks, so we need to add a complexity of \(mS\). The total complexity is \(\displaystyle O\left(\frac{n^2}{S}+mS\right)\). To minimize this value, we want these two terms to be as equal as possible. It turns out that setting \(S = \displaystyle \frac{n}{\sqrt{m}}\) is optimal, resulting in a complexity of \(\displaystyle O\left(\frac{n^2}{\displaystyle \frac{n}{\sqrt{m}}}+m\left(\frac{n}{\sqrt{m}}\right)\right)=O(n\sqrt{m})\).

In fact, if the block length is set incorrectly, the time complexity of Mo's algorithm can be greatly affected. For example, if \(m\) is of the same order as \(\sqrt n\), and the block length is mistakenly set to \(\sqrt n\), it is easy to construct a set of data that makes the time complexity \(O(n \sqrt n)\) instead of the correct \(O(n^{5/4})\).

Mo's algorithm appears very brute-force, largely because its block sorting method seems crude. One might think of sorting all intervals using a more refined method. One approach is to treat each interval \([l, r]\) as a point \((l, r)\) on a plane and build a Manhattan minimum spanning tree for all points, then transfer answers between queries along the edges of this tree. This seems like it could improve the time complexity of Mo's algorithm, but in fact, the time complexity upper bound of the block sorting method is already optimal.

Assume \(n\) and \(m\) are of the same order and \(n\) is a perfect square. Consider intervals of the form \([a \sqrt n, b \sqrt n](1 \le a, b \le \sqrt n)\). There are \(n\) such intervals. If we treat all intervals as points on a plane, the Manhattan distance between two points equals the transfer cost between the two intervals, and the minimum Manhattan distance between any two intervals is \(\sqrt n\). Therefore, the minimum time complexity to process all queries is \(O(n \sqrt n)\). Data for other cases can be constructed similarly.

Another characteristic of Mo's algorithm is that when \(n\) is fixed, the larger \(m\) is, the smaller the average transfer cost per query becomes. Some other offline algorithms also share this characteristic (e.g., Tarjan's algorithm for LCA), but Mo's algorithm shows the most pronounced change in average transfer cost with respect to \(m\).

Example & Code

Example 「National Training Team」Little Z's Socks

Problem summary:

There is a sequence \(\{c_i\}\) of length \(n\). Now \(m\) queries are given, each providing two numbers \(l,r\). Randomly select two different numbers from the indices \(l\) to \(r\), and find the probability that the two numbers are equal.

Process

Idea: Template problem for Mo's algorithm.

For interval \([l,r]\), sort in ascending order with the block number of \(l\) as the first key and \(r\) as the second key.

Then compute answers starting from the first query in the sequence. The first query is computed directly via brute force with complexity \(O(n)\). Subsequent queries are derived from the previous query's answer.

Specific approach:

For interval \([i,i]\), since the interval contains only one element, we can easily determine the answer. Then step by step move from the current interval (known answer) to the next interval.

Let \(col[i]\) denote how many times color \(i\) has appeared currently, and \(ans\) denote the current total number of feasible pairing schemes (how many ways to select a pair of socks of the same color). Then each time we move, update the answer: let the current color be \(k\). If expanding the interval, add \(\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}\) to \(ans\); if shrinking, subtract \(\dbinom{col[k]}{2}-\dbinom{col[k]-1}{2}\) from \(ans\). The answer for this query is \(\displaystyle \frac{ans}{\dbinom{r-l+1}{2}}\).

Here is an optimization: \(\displaystyle \dbinom{a}{2}=\frac{a (a-1)}{2}\).

So \(\displaystyle \dbinom{a+1}{2}-\dbinom{a}{2}=\frac{(a+1) a}{2}-\frac{a (a-1)}{2}=\frac{a}{2}\cdot (a+1-a+1)=\frac{a}{2}\cdot 2=a\).

Thus \(\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}=col[k]\).

Total algorithm complexity: \(O(n\sqrt{n} )\)

In the code below, deno represents the denominator of the answer, nume represents the numerator, sqn is the block size: \(\sqrt{n}\), arr is the input array, node is the structure storing queries, tab is the query sequence (sorted), and col is as described above.

Note: Due to the presence of ++l and --r, the order of the four while loops for moving the interval in the code below is crucial; their relative positions cannot be arbitrarily changed.

Discussion on the Order of the Four Loops

The movement process of Mo's algorithm interval is equivalent to adding elements of \([1,r]\) and deleting elements of \([1,l-1]\). Therefore,

For \(l\le r\), elements in \([1,l-1]\) are added once and then deleted once, elements in \([l,r]\) are added once, and elements in \([r+1,+\infty)\) are not added. This interval is valid.
For \(l=r+1\), elements in \([1,r]\) are added once and then deleted once, and elements in \([r+1,+\infty)\) are not added. This represents an empty interval.
For \(l>r+1\), then elements in \([r+1,l-1]\) (this interval is non-empty) are deleted once but not added, so the addition count for these elements is negative.

Therefore, if at any moment \(l>r+1\) occurs, there exists an element whose addition count is negative. This may cause issues in some problems, e.g., if we maintain all numbers in the interval using a set, we may encounter the problem of "needing to delete an element not present in the set".

There are \(4!=24\) permutations for the four while loops in the code. Assume the first loop operates on the left endpoint, giving the following \(12\) permutations (the other \(12\) are symmetric). The table below shows the correctness of these 12 versions and provides counterexamples or comments for incorrect ones.

Loop Order	Correctness	Counterexample or Comment
`l--,l++,r--,r++`	Incorrect	\(l<r<l'<r'\)
`l--,l++,r++,r--`	Incorrect	\(l<r<l'<r'\)
`l--,r--,l++,r++`	Incorrect	\(l<r<l'<r'\)
`l--,r--,r++,l++`	Correct	Proof is tedious
`l--,r++,l++,r--`	Correct
`l--,r++,r--,l++`	Correct
`l++,l--,r--,r++`	Incorrect	\(l<r<l'<r'\)
`l++,l--,r++,r--`	Incorrect	\(l<r<l'<r'\)
`l++,r++,l--,r--`	Incorrect	\(l<r<l'<r'\)
`l++,r++,r--,l--`	Incorrect	\(l<r<l'<r'\)
`l++,r--,l--,r++`	Incorrect	\(l<r<l'<r'\)
`l++,r--,r++,l--`	Incorrect	\(l<r<l'<r'\)

Only 6 out of all 24 permutations are correct, with proofs for 2 of them being tedious. Here we only provide proofs for the other 4.

The common feature of these 4 correct versions is that the first two steps expand the interval (l-- or r++), and the last two steps shrink the interval (l++ or r--). This way, the first two steps expand the interval, maintaining \(l\le r+1\); after executing the first two steps, \(l\le l'\le r'\le r\) must hold. Executing the last two steps only shrinks the interval to \([l',r']\), still satisfying \(l\le r+1\), so this approach is correct.

Implementation

Reference Code

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
constexpr int N = 50005;
int n, m, maxn;
int c[N];
long long sum;
int cnt[N];
long long ans1[N], ans2[N];

struct query {
  int l, r, id;

  bool operator<(const query &x) const {  // Overload the < operator
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];

void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}

void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  maxn = sqrt(n);
  for (int i = 1; i <= n; i++) cin >> c[i];
  for (int i = 0; i < m; i++) cin >> a[i].l >> a[i].r, a[i].id = i;
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {  // Implementation details
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
      continue;
    }
    while (l > a[i].l) add(c[--l]);
    while (r < a[i].r) add(c[++r]);
    while (l < a[i].l) del(c[l++]);
    while (r > a[i].r) del(c[r--]);
    ans1[a[i].id] = sum;
    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      long long g = gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    cout << ans1[i] << '/' << ans2[i] << '\n';
  }
  return 0;
}

Optimization of Ordinary Mo's Algorithm

Process

Consider the following data set

// Assume block size is 2 (hypothetical)
1
100
1
100

Manual simulation shows that the r pointer moves approximately 300 times. After processing the first block, we have \(l = 2, r = 100\). At this point, moving the l pointer just twice would give the answer for the fourth query. However, we instead move the r pointer to 1 to get the answer for the third query, then move it back to 100 for the fourth query, resulting in over ninety extra pointer moves. How can we optimize this? Here we use parity sorting.

What is parity sorting? Parity sorting means that for queries belonging to odd-numbered blocks, sort r in ascending order; for queries belonging to even-numbered blocks, sort r in descending order. This way, after processing an odd block, the r pointer will handle even block queries on its way back, then move toward n to process the next odd block, optimizing the number of r pointer moves. Generally, this optimization can speed up the program by about 30%.

Implementation

Sorting code:

Compact VersionNon-compact Version

// clang-format off
// There's a small detail to be discussed later
int unit; // block size
struct node {
  int l, r, id;
  bool operator < (const node &x) const {
    return l / unit == x.l / unit ? (r == x.r ? 0 : ((l / unit) & 1) ^ (r < x.r)) : l < x.l;
  }
};

struct node {
  int l, r, id;

  bool operator<(const node &x) const {
    if (l / unit != x.l / unit) return l < x.l;
    // Note: the following two lines must not use less-than-or-equal (greater-than-or-equal),
    // otherwise errors may occur (see small detail below)
    if ((l / unit) & 1) return r < x.r;
    return r > x.r;
  }
};

Small Detail

When using sort to compare two structs, it must not happen that both \(a < b\) and \(b < a\) are true simultaneously; otherwise, a runtime error will occur. See Common Mistakes.

For the compact version, without the r == x.r special case, when l belongs to the same odd block and r are equal, the problem mentioned in the small detail above will occur (simulate it manually). For the non-compact version, if written as less-than-or-equal (greater-than-or-equal), the same problem will occur.

References

Mo's Algorithm Learning Notes | Sengxian's Blog

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用