Skip to content
Tutorials Center
My learning

Topics

Lesson 117 of 225 ยท Tries and Range Queries

Square Root Decomposition and Mo's Algorithm

Learn square root decomposition in Python: split data into blocks for fast range queries and updates, then use Mo's algorithm to answer offline queries efficiently.

Some problems ask for range answers on data that changes. A prefix sum answers range sums instantly but breaks when one value changes. A sparse table answers instantly but cannot update at all. A segment tree handles both, but it can be fiddly to write. Square root decomposition is the friendly middle path: simple code, easy to reason about, and a cost of roughly O(โˆšn) per operation.

The idea is to cut the array into blocks of about โˆšn elements and keep one summary value per block. A query then touches a few loose elements at the edges plus whole blocks in the middle. In the second half of the lesson you will meet Mo's algorithm, which applies the same โˆšn thinking to the order in which you answer queries when all queries are known in advance.

The idea: blocks of size โˆšn

Take an array of n elements and choose a block size B (about โˆšn). Block b covers indexes b*B to b*B + B - 1. For a range-sum problem each block stores the sum of its elements.

TEXT
a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]      n = 12, B = 3

block 0: [3 1 4]  sum 8
block 1: [1 5 9]  sum 15
block 2: [2 6 5]  sum 13
block 3: [3 5 8]  sum 16

query sum(a[2..10]):
   a[2]            -> partial block 0   (1 element)
   blocks 1, 2     -> two whole blocks  (use stored sums)
   a[9], a[10]     -> partial block 3   (2 elements)

A query does at most 2 * (B - 1) single-element steps at the edges, plus at most n / B block steps in the middle. A point update changes one element and the sum of its block, which is O(1).

Python A block sum structure with a step counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why โˆšn? Balancing two costs

With block size B the worst case for a query is about 2B element steps at the edges plus n/B block steps in the middle. Small blocks make the middle long. Big blocks make the edges long. The total 2B + n/B is smallest when the two parts are equal, which happens near B = โˆšn, giving O(โˆšn) per query.

Let's measure that by counting steps for every possible range in an array of 100 elements:

Python Choosing the block size by counting steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Block size 1 means "one block per element", so a query scans block sums one by one; block size 100 means "one block", so a query scans elements one by one. Both extremes average 34 steps. The sweet spot sits in between: the table is lowest at B = 5 and B = 10, right around โˆš100 = 10. (The average edge cost is about B rather than 2B, because the loose parts are rarely full, which is why 5 edges out 10 here.)

Range updates with lazy blocks

Blocks also let you do range updates. To add delta to every element in [left, right], update the loose elements one by one, but for each whole block just remember a pending lazy[b] += delta. A point read then returns a[i] + lazy[block]. This is the same idea as lazy propagation in a segment tree, only simpler.

Python Range add and point query with lazy blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How it compares

Structure Build Range query Point update Notes
Plain array O(n) O(n) O(1) simplest
Prefix sums O(n) O(1) O(n) static data
Sqrt decomposition O(n) O(โˆšn) O(1) easy, very flexible
Fenwick tree O(n) O(log n) O(log n) sums only
Segment tree O(n) O(log n) O(log n) any associative op

Sqrt decomposition is slower in theory but wins on flexibility: the block summary can be anything you can maintain, such as a sorted copy of the block, a frequency table, or a count of items that satisfy a condition. Problems like "how many values in [l, r] are at least x" fit it naturally, because each block can keep a sorted list and use binary search.

Tip: the same trick works on a sequence of operations. Apply updates to a plain array, and every ~โˆšq operations rebuild the summaries from scratch. Each rebuild costs O(n), so the amortised rebuild cost is small. Sqrt-style batching also shows up in amortized analysis.

Mo's algorithm: sqrt thinking on queries

Now imagine you have many range queries and no updates, and you know all queries up front (they are offline). The question asks for something that is easy to maintain when you add or remove a single element at either end of a window, for example "how many distinct values are in a[l..r]?"

A naive approach recomputes each query from scratch, costing O(n) per query. Mo's algorithm keeps one window [curL, curR] and slides it from query to query by adding and removing single elements. The trick is to sort the queries so the window moves very little in total.

  1. Pick block size B about โˆšn.
  2. Sort queries by (l // B, r): first by the block that l falls in, then by r.
  3. Process the queries in that order. Move curL and curR to the next query's l and r, adding or removing elements one at a time and updating the answer.

Inside one block of l values, r only moves forward, so the right pointer travels at most n per block, and there are n/B blocks, which gives O(n ยท n/B) = O(nโˆšn) in total for r. The left pointer moves at most B per query inside its block, giving O(q ยท B). With B near โˆšn, the whole run costs about O((n + q) โˆšn) pointer moves.

Python Mo's algorithm: distinct values in a range

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The assert compares each answer with a brute-force len(set(...)), so a bug would raise an error instead of printing a wrong number.

Does the order really help?

Let's answer the same queries in input order and in Mo's order and count the pointer moves for a larger random input.

Python Pointer moves: input order versus Mo's order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Mo's order needs about seven times fewer moves than input order (8,691 against 61,019) and about five times fewer than recomputing every query from scratch (41,672 element touches). The gap grows with n and q: scratch work grows like q ยท n, while Mo's work grows like (n + q) ยท โˆšn.

A popular refinement is to sort r ascending in even-numbered blocks and descending in odd-numbered blocks. The right pointer then sweeps back and forth instead of jumping back to the left, which saves up to half of its travel.

Complexity summary

Technique Time Space
Build blocks O(n) O(n / B) extra
Query (sum) O(B + n / B) = O(โˆšn) O(1)
Point update (sum) O(1) O(1)
Range add (lazy) O(B + n / B) = O(โˆšn) O(n / B)
Mo's algorithm O((n + q) โˆšn) pointer moves, plus sorting O(q log q) O(n + q)

Common mistakes

  • Off-by-one in the partial blocks. The tail of the left block ends at (bl + 1) * size - 1; the head of the right block starts at br * size.
  • Forgetting the same-block case. If left and right fall in one block, scan directly; otherwise you can count elements twice or skip some.
  • Last block shorter than the others. Size the block array with a ceiling division.
  • Mo's algorithm with updates. The standard version needs a fixed array. Updates require a more advanced variant with time as a third dimension.
  • Mixing the order of pointer moves in Mo's algorithm. Grow first (extend left and right), then shrink. Otherwise the window can go negative and counts can drop below zero.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In square root decomposition with block size B, roughly how much work does one range-sum query do?

    Up to about 2B loose elements at the edges plus up to n / B whole blocks in the middle.
  2. 2. Why is the block size usually chosen near the square root of n?

    2B grows with B and n / B shrinks with B; their sum is smallest when they are about equal, at B near sqrt(n).
  3. 3. What does a point update cost in the block-sum structure?

    Change the element and adjust the sum of its one block by the difference.
  4. 4. Mo's algorithm needs which condition to work in its basic form?

    It is an offline technique: it reorders the queries, and the array stays fixed while they are answered.
  5. 5. How does Mo's algorithm sort queries (l, r)?

    Queries with their left ends in the same block are processed by increasing r, so the right pointer sweeps forward once per block.

Summary

  • Square root decomposition splits data into blocks of about โˆšn and keeps a summary for each block.
  • A range query combines loose edge elements with whole-block summaries, costing O(โˆšn); a point update is O(1) for sums.
  • Lazy values per block give range updates in O(โˆšn).
  • Choosing B near โˆšn balances edge work against the number of blocks.
  • Mo's algorithm answers offline range queries by sorting them by (l // B, r) and sliding one window with cheap add and remove steps, about O((n + q) โˆšn) in total.
  • It is slower than a segment tree in theory but easy to write and very flexible about what a block can store.

Next: Graphs