Skip to content

Basic Mo's Algorithm

Problem form

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

Explanation

Take the queries offline and sort them. Then process them in order, moving by brute force from the answer for one range to the answer for the next (one step at a time).

Sort order

Sort the ranges \([l,r]\) in increasing order, with the index of the block containing \(l\) as the first key and \(r\) as the second key.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void move(int pos, int sign) {
  // update nowAns
}

void solve() {
  BLOCK_SIZE = int(ceil(pow(n, 0.5)));
  sort(queries, queries + m);
  for (int i = 0; i < m; ++i) {
    const query &q = queries[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 discussion below assumes that \(n\) and \(m\) are of the same order of magnitude.

First comes the block decomposition step, which takes \(O(\sqrt{n}\cdot\sqrt{n}\log\sqrt{n}+n\log n)=O(n\log n)\) time.

Now we reach the heart of Mo's algorithm. We prove that it runs in \(O(n\sqrt{n})\) with an easy argument that needs nothing beyond middle-school mathematics.

Proof

Proof: let the maximum values of \(L\) in the blocks be \(\max_1,\max_2,\max_3, \cdots , \max_{\lceil\sqrt{n}\rceil}\).

By the first sort key, \(\max_1 \le \max_2 \le \cdots \le \max_{\lceil\sqrt{n}\rceil}\).

Clearly, computing the first query of each block by brute force takes \(O(n)\) time.

Consider the worst case: in every block the maximum of \(R\) is \(n\), and every change has to move \(L\) from \(\max_{i - 1}\) to \(\max_i\) or from \(\max_i\) to \(\max_{i - 1}\).

Consider \(R\) first. Within a block the values of \(R\) are already sorted, so moving it through one block takes \(O(n)\) time. Over all blocks this is \(O(n\sqrt{n})\).

The main part is \(L\). Every change costs \(O(\max_i-\max_{i-1})\), so one block takes \(O(\sqrt{n}\cdot(\max_i-\max_{i-1}))\) time.

Adding up the cost of \(L\) over all the blocks, we get:

The total time spent on \(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} \]

(a telescoping sum)

By the problem statement, \(\max_{\lceil\sqrt{n}\rceil}\) is at most \(n\), so the total time spent on \(L\) is \(O(n\sqrt{n})\) in the worst case.

Altogether, Mo's algorithm runs in \(O(n\sqrt{n})\).

For other values of \(m\), such as \(m<n\), the blocks have to be chosen differently to do better.

How should they be chosen?

Let the block size be \(S\). For any number of queries in the same block, the pointer moves a distance of \(n\), and there are \(\displaystyle \frac{n}{S}\) blocks, so the total number of moves is \(\displaystyle \frac{n^2}{S}\). Moves may also cross blocks, which adds a cost of \(mS\), so the total complexity is \(\displaystyle O\left(\frac{n^2}{S}+mS\right)\). To make this as small as possible, the two terms should be as close to equal as possible. Setting \(S\) to \(\displaystyle \frac{n}{\sqrt{m}}\) is optimal, and the complexity is then \(\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, a badly chosen block size hurts the running time of Mo's algorithm a great deal. For example, if \(m\) is of the same order of magnitude as \(\sqrt n\) and the block size is mistakenly set to \(\sqrt n\), it is easy to construct data on which the algorithm takes \(O(n \sqrt n)\) rather than the correct \(O(n^{5/4})\).

Mo's algorithm looks very much like brute force, largely because sorting by blocks looks so crude. It is tempting to sort the ranges in some seemingly finer way. One idea is to view every range \([l, r]\) as a point \((l, r)\) in the plane, build the Manhattan minimum spanning tree of all the points, and carry the answer from query to query along the edges of that tree. This looks as if it could improve the time complexity of Mo's algorithm, but in fact the upper bound achieved by sorting the queries by blocks is already optimal.

Assume that \(n\) and \(m\) are of the same order of magnitude and that \(n\) is a perfect square. Consider the ranges of the form \([a \sqrt n, b \sqrt n](1 \le a, b \le \sqrt n)\); there are \(n\) of them. If all the ranges are viewed as points in the plane, the Manhattan distance between two points is exactly the transition cost between the two ranges, and the minimum Manhattan distance between any two ranges is \(\sqrt n\), so processing all the queries takes at least \(O(n \sqrt n)\) time. Data for the other cases is constructed in a similar way.

Mo's algorithm has one more characteristic: for a fixed \(n\), the larger \(m\) is, the smaller the average transition cost per query. Some other offline algorithms share it (Tarjan's algorithm for LCA, for example), but in Mo's algorithm the average transition cost depends on \(m\) most strongly.

Example and code

Example: [Chinese national training team] Little Z's Socks

Problem statement:

There is a sequence \(\{c_i\}\) of length \(n\). You are given \(m\) queries, each consisting of two numbers \(l\) and \(r\). Two numbers at different positions are chosen at random among those with indices between \(l\) and \(r\); find the probability that they are equal.

Procedure

Approach: this is a template problem for Mo's algorithm.

Sort the ranges \([l,r]\) in increasing order, with the index of the block containing \(l\) as the first key and \(r\) as the second key.

Then compute the answers, starting from the first query of the sorted sequence. The first query is computed directly by brute force in \(O(n)\), and each later query is answered starting from the one before it.

In detail:

For a range \([i,i]\) the answer is easy to find, because the range contains a single element. From there, move step by step from the current range (whose answer is known) toward the next one.

Let \(col[i]\) be the number of times color \(i\) currently occurs, and let \(ans\) be the current number of valid ways to choose a pair (the number of ways to pick a pair of socks of the same color). Update the answer on every move. Let the current color be \(k\): when the range grows, add \(\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}\) to \(ans\); when it shrinks, subtract \(\dbinom{col[k]}{2}-\dbinom{col[k]-1}{2}\) from \(ans\). The answer to the query is \(\displaystyle \frac{ans}{\dbinom{r-l+1}{2}}\).

There is an optimization here: \(\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\).

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

The algorithm runs in \(O(n\sqrt{n} )\) overall.

In the code below, deno is the denominator of the answer and nume is its numerator, sqn is the block size \(\sqrt{n}\), arr is the input array, node is the struct that stores a query, tab is the sequence of queries (after sorting), and col is as described above.

Note: because of ++l and --r, the positions of the 4 while loops that move the range in the code below matter a great deal. Do not change their relative order arbitrarily.

Discussion of the order of the four loops

Moving the current range in Mo's algorithm amounts to having added the elements of \([1,r]\) and deleted the elements of \([1,l-1]\). Therefore:

  • If \(l\le r\), the elements of \([1,l-1]\) have in effect been added once and deleted once, the elements of \([l,r]\) have been added once, and the elements of \([r+1,+\infty)\) have not been added. This is a valid range.
  • If \(l=r+1\), the elements of \([1,r]\) have in effect been added once and deleted once, and the elements of \([r+1,+\infty)\) have not been added. In this case the range is empty.
  • If \(l>r+1\), the elements of \([r+1,l-1]\) (a non-empty range) have been deleted once without having been added, so they have been added a negative number of times.

So if \(l>r+1\) happens at some moment, some element has been added a negative number of times. This causes trouble in some problems. For example, if a set maintains all the numbers in the range, we would have to delete an element that is not in the set.

The four while loops in the code can be ordered in \(4!=24\) ways. Assume that the first loop operates on the left endpoint; this leaves the following \(12\) permutations (the other \(12\) are symmetric). The table below shows which of these 12 are correct and gives a counterexample for each incorrect one.

Loop order Correctness Counterexample or remark
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 The 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 of the 24 permutations are correct. The proofs for 2 of them are tedious, so only the other 4 are proved here.

What these 4 correct permutations have in common is that the first two steps expand the range (l-- or r++) and the last two shrink it (l++ or r--). The first two steps only expand the range, so they preserve \(l\le r+1\). Once they are done, \(l\le l'\le r'\le r\) must hold, and the last two steps merely shrink the range to \([l',r']\), so \(l\le r+1\) still holds. They are therefore correct.

Implementation

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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++) {  // the actual implementation
    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;
}

Optimizing basic Mo's algorithm

Procedure

Look at the following data:

1
2
3
4
5
// suppose the block size is 2 (hypothetically)
1 1
2 100
3 1
4 100

Simulating this by hand shows that the r pointer moves about 300 times. After the first block has been processed, \(l = 2, r = 100\). At this point, moving the l pointer twice would be enough to get the answer to the fourth query, yet we move the r pointer to 1 to get the answer to the third query and then back to 100 to get the answer to the fourth, which costs ninety-odd extra pointer moves. How can we optimize this? This is where odd-even ordering comes in.

What is odd-even ordering? For the queries in odd-numbered blocks, sort r in increasing order; for the queries in even-numbered blocks, sort r in decreasing order. After the r pointer has handled the queries of an odd block, it handles those of the even block on its way back, and then moves toward n again to handle the next odd block. This reduces the number of moves of the r pointer. In general, the optimization makes a program about 30% faster.

Implementation

The sorting code:

1
2
3
4
5
6
7
8
9
// clang-format off
// there is a small detail here, explained below
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;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
struct node {
  int l, r, id;

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

When sort compares two structs, \(a < b\) and \(b < a\) must never both be true; otherwise the program fails with a runtime error. See Common Mistakes for details.

In the crammed version, without the special case r == x.r, the problem described in the small detail above occurs when the l values lie in the same odd block and the r values are equal (simulate it by hand). In the version without cramming, using less-than-or-equal (greater-than-or-equal) causes the same problem.

References