Faangprep Logo
Log inStart free
Browse curriculum

Mo's Algorithm

Mo's algorithm is an efficient technique for answering offline range queries using square root decomposition.

Mo's algorithm answers a batch of range queries by keeping one window and sliding it from each range to the next, adding and removing a single element at a time. Since every query is known up front, they can be served in any order — so sort them by which block their left edge falls in, and the total distance the two pointers travel drops from O(N·Q) to O((N + Q)·sqrt(N)). Switch to GIVEN to see what the order they were asked in costs.

SETUP

i

0

1

2

3

4

5

6

7

8

A

1
5
2
1
3
4
2
6
3

win

Q1

0,4

Q2

3,7

Q3

1,6

Q4

6,8

Q5

5,8

Q6

0,5

Window

empty

Sum

0

Moves

0

With Mo's

21

 

6 range queries over 9 values, and every one of them is a sum of a stretch of the array. Answering each from scratch costs its whole length; instead keep ONE window and slide it from each query to the next, adding and removing a single element at a time. The window starts empty, and the only cost that matters from here is how far L and R have to walk.

Next

Blocks are 3 wide — floor(sqrt(9)) — so index 0..2 is block 0, 3..5 is block 1, and so on. Sort the queries by which block L falls in, then by R: ascending inside even blocks, descending inside odd ones, so R sweeps one way across a block and back across the next instead of returning to the start each time. New order: Q1 → Q6 → Q3 → Q5 → Q2 → Q4. The queries have not changed, only when each is served.

Array

Order

Block

3

Intuition

The Problem: If we answer range queries [L, R] one by one naively, moving from one range to another can take O(N) time, leading to O(N * Q) total time.

The Solution: What if we could re-order the queries so that we don't move our L and R pointers too much?

Mo's Algorithm (named after Mo Tao) does exactly this. It sorts the queries in a specific order so that the total movement of the L and R pointers is minimized to O((N + Q) * sqrt(N)).

Concept

Square Root Decomposition Strategy:

  • Blocking: Divide the array into blocks of size S = sqrt(N).
  • Query Sorting: Sort the queries based on the block index of their left endpoint L. If two queries have L in the same block, sort them by their right endpoint R.
  • Offline Processing: We must know all queries beforehand ("offline") to sort them. We cannot use this for online updates.

How it Works

The visualizer shows the query ranges and the current [currL, currR] window.

  1. Sort: Queries are re-ordered. Notice how the 'Start' points are grouped by blocks.
  2. Move R: The Right pointer moves monotonically significantly less often (within each block).
  3. Move L: The Left pointer stays within the small block range.
  4. Compute: We transition from the previous query range to the current one by adding/removing elements one by one.

Step-by-Step Breakdown

1. Block Size: Calculate BLOCK_SIZE = sqrt(N).
2. Sort Queries:
    - Primary Key: L / BLOCK_SIZE (Ascending)
    - Secondary Key: R (Ascending, or Zig-Zag optimization)
3. Process: Initialize currL = 0, currR = -1.
4. Transition: For each query [L, R]:
    - while (currL > L) add(--currL)
    - while (currR < R) add(++currR)
    - while (currL < L) remove(currL++)
    - while (currR > R) remove(currR--)
    - Store answer.

When to Use

  • Offline Range Queries (Sum, Frequency, Mode, Distinct Elements).
  • When the array is static (no updates to elements).
  • When N and Q are up to 10^5.

When NOT to Use

  • Online queries (must answer immediately).
  • When updates are frequent.
  • When a Segment Tree or Fenwick Tree can solve it in O(log N) (e.g., simple range sum).

How to Identify

"Range queries", "Static Array", "Offline allowed", "Hard to combine ranges (like Mode)".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Introduction

Next

Tries

Frequently Asked Questions

What does "offline" mean here?

That every query is known before any of them is answered. The algorithm works by reordering the queries, so it cannot be used when each answer must be produced before the next query arrives.

Why does sorting queries by block make it faster?

It bounds pointer movement. With blocks of size √N the left pointer moves O(√N) within a block and the right pointer sweeps the array once per block, giving O((N+Q)√N) in total rather than O(N) per query.

Why reverse the right-endpoint order in alternate blocks?

Sorting R ascending in every block sends the right pointer back to the start of the array at each block boundary. Reversing the order in odd blocks lets it snake back and forth instead, which removes those resets and cuts total travel.

When is a segment tree the better choice?

Whenever the operation combines cheaply, such as a range sum, or the array changes. Those cases get O(log N) per query, answered online, which beats O(√N) and does not require knowing the queries in advance.