On this page

Sparse Tables, Sqrt Decomposition & Mo's Algorithm

The segment tree and the Fenwick tree answer range queries in and support updates. This lesson covers three techniques that make a different trade. A sparse table gives up updates entirely and in exchange answers range-minimum (and max, gcd, AND, OR) queries in with a few lines of code. Sqrt decomposition cuts the array into about blocks and gets per operation for almost any operation you can name, including ones that do not compose nicely enough for a segment tree. Mo's algorithm takes a batch of range queries known in advance, reorders them cleverly, and answers questions like "how many distinct values are in " in total, where every online structure struggles.

All three are standard tools in competitive programming, and the sparse table in particular is the hidden engine of two structures you will meet again: the lowest-common-ancestor query in LCA, Binary Lifting & Euler Tour and the LCP queries over a suffix array in String Algorithms.

Why this exists

The range minimum query (RMQ) problem asks: given a fixed array , answer many queries "what is ?". It looks like a toy, but it is the core of a surprising amount of algorithmics. Gabow, Bentley and Tarjan showed in 1984 that RMQ and lowest common ancestor (LCA) reduce to each other in linear time: the LCA of two tree nodes is the minimum-depth node between their positions in an Euler tour, and conversely the RMQ of an array is the LCA of two nodes in its Cartesian tree. Longest-common-prefix queries between arbitrary suffixes of a string are RMQs over the LCP array. So a fast RMQ is a fast LCA and a fast suffix comparison.

The sparse table is the simplest RMQ structure with constant query time. Its idea — precompute the answer for every range whose length is a power of two, then cover any range with two of them — goes back to the parallel-algorithms work of Berkman and Vishkin around 1989–1993, and was popularised as a practical tool by Bender and Farach-Colton's 2000 paper "The LCA Problem Revisited", which used it as the building block of an -preprocessing, -query RMQ. Fischer and Heun later (2006, journal version 2011) brought the space down to bits. In practice the plain sparse table is what almost everyone writes, because it is ten lines long and fast.

Sqrt decomposition is folklore: split the input into blocks of elements, keep a summary per block, and every query touches at most two partial blocks plus whole ones. It is the "Swiss army knife" of range problems: slower than a segment tree but far more forgiving about what operations you can support. The same "keep a summary per chunk and skip chunks that cannot matter" idea is how columnar databases skip data with min/max statistics, which is why it deserves a place in an engineer's toolkit and not only a contestant's.

Mo's algorithm is named after Mo Tao, a Chinese competitive programmer to whom the technique is usually attributed (the exact origin and date are not well documented; it spread through Chinese olympiad training around 2009–2010 before becoming widely known on Codeforces). It solves the offline version of range-query problems where the answer can be maintained under "add one element at the end" and "remove one element from the end" but cannot be merged from two halves, such as counting distinct values or the sum of .

Pattern triggers

If the problem says or has…Think of…
"static array, many range min / max queries", up to Sparse table: per query
range gcd, range AND / OR, "range bitwise AND at least "Sparse table (all idempotent) plus binary search on the right end
"longest subarray such that max − min ≤ " with arbitrary endpoints, or binary search over rangesSparse table queried inside a binary search or two pointers
static range sum or xorNot a sparse table: prefix sums are and memory
point updates and range queries, but the merge is awkward or memory is tightSqrt decomposition
range update and range query with an operation that is hard to make lazySqrt decomposition with per-block tags, rebuild a block on partial updates
"jumps", "ball bounces", "next pointer changes" with updates (Holes)Sqrt decomposition on the array of pointers
"all queries are given first", "offline", "number of distinct values in "Mo's algorithm
the answer changes in when you add or remove one element at a range end, but two halves cannot be mergedMo's algorithm
offline range queries plus point updates interleavedMo's algorithm with updates (time as a third coordinate)
LCA queries, LCP between suffixes, "minimum on a path in an Euler tour"RMQ via sparse table

The literal signals: static, offline, idempotent (min, max, gcd, and, or), distinct, frequency in a range, and constraints like with a 2–5 second time limit (the zone).

Intuition & first principles

Precompute power-of-two ranges

A naive way to get RMQ is to precompute the answer for all ranges. That is time and memory: 50 GB of 32-bit integers for . The question is which small family of ranges is enough.

Take every range whose length is a power of two: for each start and each with . There are at most starts and lengths, so the family has members — about 1.7 million for . Two facts make this family enough.

  1. It is cheap to build. A range of length is two adjacent ranges of length , so its answer is one operation on two previously computed answers. Build the table level by level, .
  2. Two members cover any range. For a query of length , let , so . The range starting at of length and the range ending at of length both lie inside , and since they overlap and together cover all of it.

For the minimum, covering the range twice is harmless: the minimum of a set does not change if some elements are counted twice. That is the whole trick. The formal property is idempotence: .

Idempotent versus not

OperationAssociativeIdempotent ()Sparse table query
min, maxyesyes
gcd, lcmyesyes (plus the cost of one gcd)
bitwise AND, ORyesyes
"first non-null", "leftmost" ()yesyes
sum, productyesno with disjoint pieces
bitwise XORyesno () with disjoint pieces
matrix product, function compositionyesno, and not commutative, pieces in order

For a non-idempotent operation you can still use the table: decompose into disjoint power-of-two pieces (the binary representation of the length gives at most of them) and combine left to right. That costs , which a segment tree matches while also supporting updates, so in practice the sparse table is used almost only for idempotent operations. For static sums, prefix sums are strictly better.

Blocks: the balance

Now suppose the array changes. The sparse table is dead: changing one element invalidates up to table entries (every range containing it, at every level — of them in total). The other extreme, a plain array, updates in but queries in .

Split the array into blocks of size and store one summary per block (say the block's sum). A point update changes one element and one block summary: . A query walks element by element through the partial block at the left end, jumps block by block through the middle, and walks element by element through the partial block at the right end. The partial ends cost at most steps and the middle at most . Minimising gives and a query cost of . For that is about 2,000 steps, versus 1,000,000 for the naive scan and about 40 node visits for a segment tree.

Why bother when a segment tree is faster? Because the block summary only has to support "rebuild from scratch in " and "combine with a query in or ". Many summaries can do that but cannot be merged across two children cheaply: a sorted copy of the block (for "how many elements in "), a frequency table, a convex hull, the "where does a ball leave this block" pointers in the Holes problem. Sqrt decomposition lets you use any of them.

Reordering offline queries

Mo's algorithm starts from a different observation. Suppose you maintain the answer for a current window together with whatever counts it needs, and you can move either end by one position in : add , remove , add , remove . Then answering a query costs moves from the previous window. Answered in the order given, an adversary can make every query jump across the array: moves, for .

But if all queries are known up front you may answer them in any order. Think of each query as a point in the plane; the total cost is the length of a path visiting all points in the Manhattan metric. Finding the shortest such path is a travelling-salesman problem, but a good-enough path is easy: cut the -axis into strips of width , visit strips left to right, and within a strip sweep in one direction. Then moves monotonically within each strip ( moves per strip) and moves at most per query. With the total is — about moves for , versus up to unsorted.

Mechanics

Building and querying a sparse table

Let be the answer on . Then

for . A query on with is

is either precomputed in an array (lg[1] = 0, lg[i] = lg[i // 2] + 1) or taken from a hardware instruction: L.bit_length() - 1 in Python, 31 - Integer.numberOfLeadingZeros(L) in Java, std::bit_width(L) - 1 in C++20, 31 - Math.clz32(L) in JavaScript.

flowchart TD
    A0["level 0 = the array<br/>5 2 4 7 1 3 6 8"] --> A1["level 1: min of entries i and i+1 below<br/>2 2 4 1 1 3 6"]
    A1 --> A2["level 2: min of entries i and i+2 below<br/>2 1 1 1 1"]
    A2 --> A3["level 3: min of entries i and i+4 below<br/>1"]
    Q["query(1, 6): length 6, k = 2"] --> L["left piece: level 2, start 1, covers 1..4"]
    Q --> R["right piece: level 2, start 3, covers 3..6"]
    L --> ANS["min(1, 1) = 1<br/>indices 3..4 counted twice: harmless"]
    R --> ANS

Trace: building the min sparse table for a = [5, 2, 4, 7, 1, 3, 6, 8] (computed by script):

krange length valid starts example entry
010..75, 2, 4, 7, 1, 3, 6, 8
120..62, 2, 4, 1, 1, 3, 6
240..42, 1, 1, 1, 1
380..01

Total entries: , each computed with one min.

Trace: queries on the same table:

query lengthleft pieceright pieceanswer
[0, 7]83 (0..7) (0..7)1
[1, 3]31 (1..2) (2..3)2
[5, 7]31 (5..6) (6..7)3
[2, 6]52 (2..5) (3..6)1
[3, 3]107

When the length is an exact power of two both pieces are the same entry; that is fine for idempotent operations.

Sum queries on the same table, disjoint pieces. With instead of min, walk from the top down and take a piece whenever it fits:

querypieces taken (level, start → value)sum
[2, 5](2, 2 → 15)15
[1, 6](2, 1 → 14), (1, 5 → 9)23
[0, 6](2, 0 → 18), (1, 4 → 4), (0, 6 → 6)28

The number of pieces equals the number of 1 bits in the length (7 = 111₂ → 3 pieces).

The disjoint sparse table

A disjoint sparse table gets queries for any associative operation, idempotent or not, at the same cost. At level , the array is cut into blocks of size ; around each block's midpoint we store suffix aggregates for left of the midpoint and prefix aggregates for right of it. A query with uses the level equal to the index of the highest set bit of : at that level, and fall in the same block but on opposite sides of its midpoint, so the answer is exactly suffix[h][l] ∘ prefix[h][r] — two disjoint pieces, nothing counted twice. It is less known than the ordinary sparse table but appears in contest libraries for range products modulo a prime and range composition of affine functions. A runnable version is in Variations.

Sqrt decomposition: point update, range query

flowchart LR
    subgraph B0["block 0: indices 0..2"]
        a0["5"] --- a1["2"] --- a2["4"]
    end
    subgraph B1["block 1: indices 3..5"]
        a3["7"] --- a4["1"] --- a5["3"]
    end
    subgraph B2["block 2: indices 6..7"]
        a6["6"] --- a7["8"]
    end
    S0["sum = 11"] -.-> B0
    S1["sum = 11"] -.-> B1
    S2["sum = 14"] -.-> B2

With and the block sums are 11, 11, 14.

Trace: sum(1, 6), then set(4, 10), then two more queries (computed by script):

operationleft partialwhole blocksright partialresultblock sums after
sum(1, 6)block 1 = 112311, 11, 14
set(4, 10)–block 1 += 10 − 1––11, 20, 14
sum(3, 5)noneblock 1 = 20none2011, 20, 14
sum(0, 7)noneblock 0 = 11, block 1 = 204511, 20, 14

The query walks: while is not at a block start, take ; then while a whole block fits in , take its summary; then finish element by element. Each loop runs at most , and times.

Range updates. For "add to every element of " keep a lazy tag per block: whole blocks get tag += x and sum += x * size, partial blocks are updated element by element. A query adds tag to every element it reads individually. Every operation stays . For operations that do not compose into a tag (say "assign then add" with order-dependent semantics on a sorted block), the universal fallback is to rebuild a partial block from scratch in or .

Choosing the block size. balances the two costs only if they are equally expensive. In general, if partial-block work costs per operation and whole-block work costs , pick to equalise them. Example: blocks kept sorted for "count elements in with point updates". A query does element checks plus binary searches of each; an update re-sorts one block in (shift one element into place). Equalising with gives . In practice, measure: constant factors (cache behaviour of the per-element loop versus the per-block loop) often move the optimum by a factor of 2 to 4 from the theoretical value.

The sqrt tree (mention)

The sqrt tree (described on cp-algorithms) applies the block idea recursively: blocks of size , inside them blocks of size , and so on, storing prefix and suffix aggregates for every block and a table of between-block aggregates. Any range is then answered by at most one level, giving queries for any associative operation after preprocessing, with point updates in . It is rarely needed in contests (the disjoint sparse table covers most uses) but is a neat demonstration that "blocks of " is a recursive idea, not only a one-level trick.

Mo's algorithm

  1. Choose a block size (start with ; the optimum is , see Complexity).
  2. Sort the queries by . The odd-even refinement sorts ascending in even-numbered blocks and descending in odd-numbered ones, so sweeps back instead of jumping to the left at every block boundary.
  3. Keep the current window , initially empty (, ), and the data needed to answer the query (for distinct values, a count per value and the number of nonzero counts).
  4. For each query in sorted order, move and one step at a time, calling add(i) or remove(i), until the window equals ; record the answer at the query's original index.

Order the four loops so the window never becomes "negative": extend first (R right, L left), then shrink (R left, L right). Shrinking first can momentarily make and decrement counts below zero, which is harmless for some answers and fatal for others.

flowchart TD
    S["sort queries by block of l, then r (odd-even)"] --> W["window L = 0, R = -1, counts all 0"]
    W --> NQ{"next query (l, r)?"}
    NQ -->|"none left"| OUT["return answers in original order"]
    NQ -->|"yes"| E1["while R < r: R++, add(R)"]
    E1 --> E2["while L > l: L--, add(L)"]
    E2 --> S1["while R > r: remove(R), R--"]
    S1 --> S2["while L < l: remove(L), L++"]
    S2 --> REC["ans[query index] = distinct"]
    REC --> NQ

Trace: distinct values with Mo's algorithm on arr = [1, 2, 1, 3, 2, 2, 4, 1], queries in input order (0, 2), (1, 5), (0, 7), (5, 6), (3, 3), (2, 4), block size , odd-even order (computed by script):

orderquery (index)block of moves this querymoves totalcounts after (value: count)distinct
1(0, 2) #003 (add 0, 1, 2)31:2, 2:12
2(1, 5) #104 (add 3, 4, 5; remove 0)71:1, 2:3, 3:13
3(0, 7) #203 (add 6, 7; add 0)101:3, 2:3, 3:1, 4:14
4(2, 4) #51 (odd: descending)5 (remove 7, 6, 5; remove 0, 1)151:1, 2:1, 3:13
5(3, 3) #412 (remove 4; remove 2)173:11
6(5, 6) #325 (add 4, 5, 6; remove 3, 4)222:1, 4:12

Answers in input order: [2, 3, 4, 2, 1, 3]. Total 22 pointer moves; the plain order (always ascending) needs 24 here and the input order 23 — on eight elements the orderings barely differ, but on random queries the difference is the one between 2.6 × 10⁷ and 5.3 × 10⁹ moves (measured below).

Mo's algorithm with updates (mention)

If the queries are interleaved with point updates, add time as a third coordinate: a query is where is the number of updates before it. The window state is now , and moving forward or back applies or undoes one update (if the updated position lies inside , remove the old value and add the new one). Sort by with ; the total work is for . The classic exercise is Codeforces 940F, in the practice ladder below.

Mo's on trees (mention)

Path queries on a tree ("distinct colours on the path ") can be turned into range queries over an Euler tour that records each vertex at entry and exit: a vertex appearing twice in the range cancels, and the LCA is added separately when it is not an endpoint. That needs the Euler tour and LCA machinery of LCA, Binary Lifting & Euler Tour.

The ladder: brute force → better → optimal

Ladder 1: static range minimum

Rung 0: scan each query, . No preprocessing; each query loops over elements. For with random ranges, about comparisons. Fine for .

Rung 1: all pairs, preprocessing, query. best[l][r] = min(best[l][r-1], a[r]). Memory kills it at (400 million entries).

Rung 2: sqrt decomposition, preprocessing, query. Block minima; at most elements plus blocks per query. Also supports point updates (rebuild one block's minimum in ).

Rung 3: segment tree, preprocessing, query. Supports updates. Covered in Segment Trees in Depth.

Rung 4: sparse table, preprocessing, query. Two table reads and one min. For this is the winner: queries cost operations, not .

Rung 5 (theory): preprocessing and query. Bender and Farach-Colton's block scheme for the case, or Fischer and Heun's Cartesian-tree-signature scheme for general arrays: blocks of size , a sparse table over block minima (), and a lookup table indexed by the shape of each tiny block. Asymptotically optimal, rarely faster in practice than the plain sparse table for .

RungPreprocessingQueryUpdatesMemory
0 scannone extra
1 all pairsno
2 sqrt blocks extra
3 segment tree
4 sparse tableno
5 Fischer–Heunno bits

Ladder 2: distinct values in a range

Rung 0: hash set per query, . Simple, operations for .

Rung 1: Mo's algorithm, . Offline; add/remove updates a count array. About moves for ; passes in C++ comfortably, in Python only with care.

Rung 2: offline sweep with a Fenwick tree, . Sort queries by ; sweep from left to right; for each value keep only its last occurrence marked with a 1 in a Fenwick tree (unmark the previous occurrence when a new one arrives). Then the answer to is the number of marks in . Faster, but the trick is specific to "distinct count"; Mo's handles any add/remove-maintainable statistic.

Rung 3: persistent segment tree, online, per query. The same last-occurrence idea, with one persistent version per . Needed when queries must be answered online (each depends on the previous answer).

RungOnline?TimeGeneralises to
hash set per queryyesanything
Mo's algorithmnoany add/remove-maintainable answer
offline sweep + Fenwickno"count of distinct" style problems
persistent segment treeyessame, online

Correctness

Sparse table build

Claim. After building level , for every valid .

Proof by induction on . For the range has one element and . For , the range is the concatenation of and , both of length and both valid starts at level (the second ends at ). By the induction hypothesis their entries hold the aggregates of those halves, and by associativity the aggregate of the concatenation is their combination.

The overlapping query (idempotence)

Claim. If is associative and idempotent ( for all ), then for ,

Proof. Let and . Since , both pieces and lie inside (and ). Since , , so : the pieces overlap or touch. Write the left piece as and the right piece as , where , (the overlap, non-empty) and , with juxtaposition meaning -aggregation. By associativity,

where because is itself an element of the set and every element is idempotent. is exactly the aggregate of in order.

Two remarks. First, commutativity is not needed: the overlap is a suffix of the left piece and a prefix of the right piece, so order is preserved. "Leftmost element", , is idempotent and non-commutative and works. Second, the proof needs for aggregates, not just for array elements; for min, max, gcd, AND and OR every value is idempotent so this is automatic. For XOR it fails: , and the query would return , which is wrong whenever the overlap is non-zero.

Disjoint decomposition for sums

The top-down greedy takes level when . Invariant: before considering level , the remaining length is less than . Initially true because starts at . If the remaining length is at least we take the piece and the remainder is less than ; otherwise it already is. After level 0 the remaining length is less than 1, so it is 0: the pieces exactly tile , disjointly and in order, and associativity gives the right aggregate. At most one piece per level: .

Sqrt decomposition

Invariant: blocks[j] equals the sum of the elements currently in block . The constructor establishes it; set(i, v) changes exactly one element of block and adjusts that block's sum by the difference, preserving it. A query partitions into three consecutive parts — elements before the first block boundary at or after , the whole blocks that fit, and the remaining elements — and adds each part using either raw elements or (by the invariant) exact block sums. Every index in is counted exactly once.

Mo's algorithm

Invariant: after processing a query, the data structure (counts and distinct) describes exactly the multiset . Initially the window is empty and all counts are zero. Each add(i) is called exactly when enters the window and each remove(i) exactly when it leaves; distinct changes precisely when a count moves between 0 and 1. Because extensions happen before shrinks, the window never has , so no count goes negative. When the loops stop, , so the recorded answer is the number of distinct values in . The order of queries is irrelevant to correctness, only to cost; answers are stored at the original indices.

Complexity

Sparse table

  • Build: operations. For : 20 levels, about entries.
  • Query: for idempotent operations (one log, two reads, one combine; for gcd the combine itself is ). for the disjoint decomposition.
  • Memory: — the real constraint. with 32-bit values and full rows is 80 MB; trimming row to entries saves little. Store indices instead of values only if you need the position of the minimum.
  • Cache: lay the table out level-major (st[k][i]), so the build streams through two rows sequentially. A query reads two entries of the same row, at most apart, usually two cache misses for large . A segment tree query typically touches nodes, more of them in cache near the root; for both are fast and the difference only shows at .

Sqrt decomposition

With block size : point update for sums (or if the block summary must be rebuilt, as for minima), range query . At both are . Memory extra. Constants are small and access is sequential, so a sqrt decomposition with often runs within a factor of 3–5 of a segment tree despite the worse asymptotics.

Mo's algorithm: the bound

Theorem. With block size and the order , the total number of pointer moves over queries on an array of length is , which is for , and for .

Proof. Count the two pointers separately.

Right pointer. Within one block of left endpoints, queries are sorted by , so moves monotonically: at most moves for the whole block. When moving to the next block, may jump back by at most . There are at most blocks, so moves in total.

Left pointer. Between two consecutive queries in the same block, both values lie in an interval of length , so moves at most : over all such pairs. When the sorted order moves from block to a later block , moves at most . Blocks are visited in increasing order, so these terms telescope: the sum of over all block changes is at most , and the extra appears once per change (at most changes). Block changes therefore cost in total. Overall: .

Sum: . The function is minimised at , where it equals . With it is .

Each move costs one add or remove. If those cost , the total time is including the sort. If they cost (for example, maintaining a sorted multiset), multiply.

Measured (script, random queries with uniform endpoints, total pointer moves):

input orderplain sort, odd-even, odd-even, Hilbert order
100,000100,0005,331,096,86941,890,95926,353,868(same )27,773,86531,622,776
100,00010,000–30,847,57016,485,8008,398,0868,850,54910,000,000
30,000200,000–16,730,10814,184,37211,184,58211,778,03213,416,407

Three lessons from the table. Sorting is worth a factor of about 200 over the input order. The odd-even trick saves roughly 20–45%. And the block size matters when and differ: halves the work in the row.

Hilbert order. Instead of strips, sort queries by their index along a Hilbert curve over the grid (proposed for Mo's algorithm in a 2017 Codeforces blog post by the user gepardo). The curve visits nearby points consecutively, so consecutive queries are close in both coordinates, and there is no block size to tune. In the measurements above it lands within about 5% of the tuned odd-even order and beats the untuned one whenever . The theoretical guarantee is the same .

Implementation

Three structures, the same test data in every language:

  1. SparseTable(a, op) with query(l, r) (, idempotent op) and fold(l, r) (, any associative op, disjoint pieces). Tested with min, max, gcd and sum.
  2. SqrtSum(a) with set(i, v) and query(l, r) on blocks of size .
  3. moDistinct(arr, queries) — Mo's algorithm, odd-even order, block , coordinate-compressed counts.
from math import gcd, isqrt
from typing import Callable


class SparseTable:
    def __init__(self, a: list[int], op: Callable[[int, int], int]):
        self.op = op
        n = len(a)
        self.table = [a[:]]                       # table[k][i] = op over a[i .. i + 2^k - 1]
        k = 1
        while (1 << k) <= n:
            prev, half = self.table[-1], 1 << (k - 1)
            self.table.append([op(prev[i], prev[i + half]) for i in range(n - (1 << k) + 1)])
            k += 1

    def query(self, l: int, r: int) -> int:       # O(1); op must be idempotent
        k = (r - l + 1).bit_length() - 1
        return self.op(self.table[k][l], self.table[k][r - (1 << k) + 1])

    def fold(self, l: int, r: int) -> int:        # O(log n); any associative op
        result = None
        for k in range(len(self.table) - 1, -1, -1):
            if l + (1 << k) - 1 <= r:
                v = self.table[k][l]
                result = v if result is None else self.op(result, v)
                l += 1 << k
        return result


class SqrtSum:
    def __init__(self, a: list[int]):
        self.a = a[:]
        n = len(a)
        b = isqrt(n)
        if b * b < n:
            b += 1
        self.b = max(1, b)
        self.blocks = [0] * ((n + self.b - 1) // self.b)
        for i, v in enumerate(a):
            self.blocks[i // self.b] += v

    def set(self, i: int, v: int) -> None:
        self.blocks[i // self.b] += v - self.a[i]
        self.a[i] = v

    def query(self, l: int, r: int) -> int:
        s, b = 0, self.b
        while l <= r and l % b != 0:              # left partial block
            s += self.a[l]
            l += 1
        while l + b - 1 <= r:                     # whole blocks
            s += self.blocks[l // b]
            l += b
        while l <= r:                             # right partial block
            s += self.a[l]
            l += 1
        return s


def mo_distinct(arr: list[int], queries: list[tuple[int, int]]) -> list[int]:
    ids = {v: i for i, v in enumerate(sorted(set(arr)))}
    comp = [ids[v] for v in arr]
    block = max(1, isqrt(len(arr)))

    def key(qi: int) -> tuple[int, int]:
        l, r = queries[qi]
        b = l // block
        return (b, r if b % 2 == 0 else -r)       # odd-even ordering

    cnt = [0] * len(ids)
    distinct = 0
    cur_l, cur_r = 0, -1
    ans = [0] * len(queries)
    for qi in sorted(range(len(queries)), key=key):
        l, r = queries[qi]
        while cur_r < r:
            cur_r += 1
            cnt[comp[cur_r]] += 1
            distinct += cnt[comp[cur_r]] == 1
        while cur_l > l:
            cur_l -= 1
            cnt[comp[cur_l]] += 1
            distinct += cnt[comp[cur_l]] == 1
        while cur_r > r:
            cnt[comp[cur_r]] -= 1
            distinct -= cnt[comp[cur_r]] == 0
            cur_r -= 1
        while cur_l < l:
            cnt[comp[cur_l]] -= 1
            distinct -= cnt[comp[cur_l]] == 0
            cur_l += 1
        ans[qi] = distinct
    return ans


if __name__ == "__main__":
    a = [5, 2, 4, 7, 1, 3, 6, 8]
    mn = SparseTable(a, min)
    assert [mn.query(0, 7), mn.query(1, 3), mn.query(5, 7), mn.query(2, 6), mn.query(3, 3)] == [1, 2, 3, 1, 7]
    mx = SparseTable(a, max)
    assert mx.query(0, 3) == 7 and mx.query(4, 7) == 8
    g = SparseTable([12, 18, 24, 36, 9], gcd)
    assert [g.query(0, 3), g.query(3, 4), g.query(0, 4)] == [6, 9, 3]
    sm = SparseTable(a, lambda x, y: x + y)
    assert [sm.fold(2, 5), sm.fold(1, 6), sm.fold(0, 6)] == [15, 23, 28]

    sq = SqrtSum(a)
    assert sq.blocks == [11, 11, 14] and sq.query(1, 6) == 23
    sq.set(4, 10)
    assert sq.blocks == [11, 20, 14] and sq.query(3, 5) == 20 and sq.query(0, 7) == 45

    arr = [1, 2, 1, 3, 2, 2, 4, 1]
    qs = [(0, 2), (1, 5), (0, 7), (5, 6), (3, 3), (2, 4)]
    assert mo_distinct(arr, qs) == [2, 3, 4, 2, 1, 3]
    print("all tests pass")
import java.util.*;
import java.util.function.IntBinaryOperator;

public class RangeStructures {
    static final class SparseTable {
        final int[][] table;
        final IntBinaryOperator op;

        SparseTable(int[] a, IntBinaryOperator op) {
            this.op = op;
            int n = a.length, levels = 32 - Integer.numberOfLeadingZeros(n);
            table = new int[levels][];
            table[0] = a.clone();
            for (int k = 1; k < levels; k++) {
                int half = 1 << (k - 1), len = n - (1 << k) + 1;
                table[k] = new int[len];
                for (int i = 0; i < len; i++) table[k][i] = op.applyAsInt(table[k - 1][i], table[k - 1][i + half]);
            }
        }

        int query(int l, int r) {                   // O(1), idempotent op
            int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
            return op.applyAsInt(table[k][l], table[k][r - (1 << k) + 1]);
        }

        int fold(int l, int r) {                    // O(log n), any associative op
            boolean first = true;
            int result = 0;
            for (int k = table.length - 1; k >= 0; k--) {
                if (l + (1 << k) - 1 <= r) {
                    int v = table[k][l];
                    result = first ? v : op.applyAsInt(result, v);
                    first = false;
                    l += 1 << k;
                }
            }
            return result;
        }
    }

    static final class SqrtSum {
        final long[] a, blocks;
        final int b;

        SqrtSum(int[] src) {
            int n = src.length;
            int s = (int) Math.sqrt(n);
            while (s * s < n) s++;
            b = Math.max(1, s);
            a = new long[n];
            blocks = new long[(n + b - 1) / b];
            for (int i = 0; i < n; i++) { a[i] = src[i]; blocks[i / b] += src[i]; }
        }

        void set(int i, long v) { blocks[i / b] += v - a[i]; a[i] = v; }

        long query(int l, int r) {
            long s = 0;
            while (l <= r && l % b != 0) s += a[l++];
            while (l + b - 1 <= r) { s += blocks[l / b]; l += b; }
            while (l <= r) s += a[l++];
            return s;
        }
    }

    static int[] moDistinct(int[] arr, int[][] queries) {
        int n = arr.length, q = queries.length;
        int[] sorted = Arrays.stream(arr).distinct().sorted().toArray();
        int[] comp = new int[n];
        for (int i = 0; i < n; i++) comp[i] = Arrays.binarySearch(sorted, arr[i]);
        int block = Math.max(1, (int) Math.sqrt(n));
        Integer[] order = new Integer[q];
        for (int i = 0; i < q; i++) order[i] = i;
        Arrays.sort(order, (x, y) -> {
            int bx = queries[x][0] / block, by = queries[y][0] / block;
            if (bx != by) return Integer.compare(bx, by);
            return (bx % 2 == 0) ? Integer.compare(queries[x][1], queries[y][1])
                                 : Integer.compare(queries[y][1], queries[x][1]);
        });
        int[] cnt = new int[sorted.length], ans = new int[q];
        int distinct = 0, curL = 0, curR = -1;
        for (int qi : order) {
            int l = queries[qi][0], r = queries[qi][1];
            while (curR < r) if (++cnt[comp[++curR]] == 1) distinct++;
            while (curL > l) if (++cnt[comp[--curL]] == 1) distinct++;
            while (curR > r) if (--cnt[comp[curR--]] == 0) distinct--;
            while (curL < l) if (--cnt[comp[curL++]] == 0) distinct--;
            ans[qi] = distinct;
        }
        return ans;
    }

    static int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[] a = {5, 2, 4, 7, 1, 3, 6, 8};
        SparseTable mn = new SparseTable(a, Math::min);
        check(mn.query(0, 7) == 1 && mn.query(1, 3) == 2 && mn.query(5, 7) == 3, "min 1");
        check(mn.query(2, 6) == 1 && mn.query(3, 3) == 7, "min 2");
        SparseTable mx = new SparseTable(a, Math::max);
        check(mx.query(0, 3) == 7 && mx.query(4, 7) == 8, "max");
        SparseTable g = new SparseTable(new int[]{12, 18, 24, 36, 9}, RangeStructures::gcd);
        check(g.query(0, 3) == 6 && g.query(3, 4) == 9 && g.query(0, 4) == 3, "gcd");
        SparseTable sm = new SparseTable(a, Integer::sum);
        check(sm.fold(2, 5) == 15 && sm.fold(1, 6) == 23 && sm.fold(0, 6) == 28, "sum");

        SqrtSum sq = new SqrtSum(a);
        check(Arrays.equals(sq.blocks, new long[]{11, 11, 14}) && sq.query(1, 6) == 23, "sqrt 1");
        sq.set(4, 10);
        check(Arrays.equals(sq.blocks, new long[]{11, 20, 14}) && sq.query(3, 5) == 20 && sq.query(0, 7) == 45, "sqrt 2");

        int[] arr = {1, 2, 1, 3, 2, 2, 4, 1};
        int[][] qs = {{0, 2}, {1, 5}, {0, 7}, {5, 6}, {3, 3}, {2, 4}};
        check(Arrays.equals(moDistinct(arr, qs), new int[]{2, 3, 4, 2, 1, 3}), "mo");
        System.out.println("all tests pass");
    }
}
#include <algorithm>
#include <bit>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

struct SparseTable {
    std::vector<std::vector<int>> table;
    std::function<int(int, int)> op;

    SparseTable(const std::vector<int>& a, std::function<int(int, int)> f) : op(std::move(f)) {
        int n = static_cast<int>(a.size());
        int levels = std::bit_width(static_cast<unsigned>(n));
        table.assign(levels, {});
        table[0] = a;
        for (int k = 1; k < levels; ++k) {
            int half = 1 << (k - 1), len = n - (1 << k) + 1;
            table[k].resize(len);
            for (int i = 0; i < len; ++i) table[k][i] = op(table[k - 1][i], table[k - 1][i + half]);
        }
    }

    int query(int l, int r) const {               // O(1), idempotent op
        int k = std::bit_width(static_cast<unsigned>(r - l + 1)) - 1;
        return op(table[k][l], table[k][r - (1 << k) + 1]);
    }

    int fold(int l, int r) const {                // O(log n), any associative op
        bool first = true;
        int result = 0;
        for (int k = static_cast<int>(table.size()) - 1; k >= 0; --k) {
            if (l + (1 << k) - 1 <= r) {
                int v = table[k][l];
                result = first ? v : op(result, v);
                first = false;
                l += 1 << k;
            }
        }
        return result;
    }
};

struct SqrtSum {
    std::vector<long long> a, blocks;
    int b;

    explicit SqrtSum(const std::vector<int>& src) : a(src.begin(), src.end()) {
        int n = static_cast<int>(src.size());
        int s = static_cast<int>(std::sqrt(static_cast<double>(n)));
        while (s * s < n) ++s;
        b = std::max(1, s);
        blocks.assign((n + b - 1) / b, 0);
        for (int i = 0; i < n; ++i) blocks[i / b] += src[i];
    }

    void set(int i, long long v) { blocks[i / b] += v - a[i]; a[i] = v; }

    long long query(int l, int r) const {
        long long s = 0;
        while (l <= r && l % b != 0) s += a[l++];
        while (l + b - 1 <= r) { s += blocks[l / b]; l += b; }
        while (l <= r) s += a[l++];
        return s;
    }
};

std::vector<int> moDistinct(const std::vector<int>& arr, const std::vector<std::pair<int, int>>& queries) {
    int n = static_cast<int>(arr.size()), q = static_cast<int>(queries.size());
    std::vector<int> vals(arr);
    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
    std::vector<int> comp(n);
    for (int i = 0; i < n; ++i)
        comp[i] = static_cast<int>(std::lower_bound(vals.begin(), vals.end(), arr[i]) - vals.begin());
    int block = std::max(1, static_cast<int>(std::sqrt(static_cast<double>(n))));
    std::vector<int> order(q);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](int x, int y) {
        int bx = queries[x].first / block, by = queries[y].first / block;
        if (bx != by) return bx < by;
        return (bx % 2 == 0) ? queries[x].second < queries[y].second : queries[x].second > queries[y].second;
    });
    std::vector<int> cnt(vals.size(), 0), ans(q);
    int distinct = 0, curL = 0, curR = -1;
    for (int qi : order) {
        auto [l, r] = queries[qi];
        while (curR < r) if (++cnt[comp[++curR]] == 1) ++distinct;
        while (curL > l) if (++cnt[comp[--curL]] == 1) ++distinct;
        while (curR > r) if (--cnt[comp[curR--]] == 0) --distinct;
        while (curL < l) if (--cnt[comp[curL++]] == 0) --distinct;
        ans[qi] = distinct;
    }
    return ans;
}

int main() {
    std::vector<int> a{5, 2, 4, 7, 1, 3, 6, 8};
    SparseTable mn(a, [](int x, int y) { return std::min(x, y); });
    assert(mn.query(0, 7) == 1 && mn.query(1, 3) == 2 && mn.query(5, 7) == 3);
    assert(mn.query(2, 6) == 1 && mn.query(3, 3) == 7);
    SparseTable mx(a, [](int x, int y) { return std::max(x, y); });
    assert(mx.query(0, 3) == 7 && mx.query(4, 7) == 8);
    SparseTable g({12, 18, 24, 36, 9}, [](int x, int y) { return std::gcd(x, y); });
    assert(g.query(0, 3) == 6 && g.query(3, 4) == 9 && g.query(0, 4) == 3);
    SparseTable sm(a, [](int x, int y) { return x + y; });
    assert(sm.fold(2, 5) == 15 && sm.fold(1, 6) == 23 && sm.fold(0, 6) == 28);

    SqrtSum sq(a);
    assert((sq.blocks == std::vector<long long>{11, 11, 14}) && sq.query(1, 6) == 23);
    sq.set(4, 10);
    assert((sq.blocks == std::vector<long long>{11, 20, 14}) && sq.query(3, 5) == 20 && sq.query(0, 7) == 45);

    std::vector<int> arr{1, 2, 1, 3, 2, 2, 4, 1};
    std::vector<std::pair<int, int>> qs{{0, 2}, {1, 5}, {0, 7}, {5, 6}, {3, 3}, {2, 4}};
    assert((moDistinct(arr, qs) == std::vector<int>{2, 3, 4, 2, 1, 3}));
    std::cout << "all tests pass\n";
}
type Op = (x: number, y: number) => number;

class SparseTable {
  table: number[][];
  op: Op;

  constructor(a: number[], op: Op) {
    this.op = op;
    const n = a.length;
    this.table = [a.slice()];
    for (let k = 1; (1 << k) <= n; k++) {
      const prev = this.table[k - 1], half = 1 << (k - 1), len = n - (1 << k) + 1;
      const row = new Array<number>(len);
      for (let i = 0; i < len; i++) row[i] = op(prev[i], prev[i + half]);
      this.table.push(row);
    }
  }

  query(l: number, r: number): number {          // O(1), idempotent op
    const k = 31 - Math.clz32(r - l + 1);
    return this.op(this.table[k][l], this.table[k][r - (1 << k) + 1]);
  }

  fold(l: number, r: number): number {           // O(log n), any associative op
    let result: number | null = null;
    for (let k = this.table.length - 1; k >= 0; k--) {
      if (l + (1 << k) - 1 <= r) {
        const v = this.table[k][l];
        result = result === null ? v : this.op(result, v);
        l += 1 << k;
      }
    }
    return result as number;
  }
}

class SqrtSum {
  a: number[];
  blocks: number[];
  b: number;

  constructor(src: number[]) {
    const n = src.length;
    let s = Math.floor(Math.sqrt(n));
    while (s * s < n) s++;
    this.b = Math.max(1, s);
    this.a = src.slice();
    this.blocks = new Array(Math.ceil(n / this.b)).fill(0);
    src.forEach((v, i) => { this.blocks[Math.floor(i / this.b)] += v; });
  }

  set(i: number, v: number): void {
    this.blocks[Math.floor(i / this.b)] += v - this.a[i];
    this.a[i] = v;
  }

  query(l: number, r: number): number {
    const b = this.b;
    let s = 0;
    while (l <= r && l % b !== 0) s += this.a[l++];
    while (l + b - 1 <= r) { s += this.blocks[Math.floor(l / b)]; l += b; }
    while (l <= r) s += this.a[l++];
    return s;
  }
}

function moDistinct(arr: number[], queries: [number, number][]): number[] {
  const vals = [...new Set(arr)].sort((x, y) => x - y);
  const id = new Map<number, number>();
  vals.forEach((v, i) => id.set(v, i));
  const comp = arr.map((v) => id.get(v) as number);
  const block = Math.max(1, Math.floor(Math.sqrt(arr.length)));
  const order = queries.map((_, i) => i).sort((x, y) => {
    const bx = Math.floor(queries[x][0] / block), by = Math.floor(queries[y][0] / block);
    if (bx !== by) return bx - by;
    return bx % 2 === 0 ? queries[x][1] - queries[y][1] : queries[y][1] - queries[x][1];
  });
  const cnt = new Array<number>(vals.length).fill(0);
  const ans = new Array<number>(queries.length).fill(0);
  let distinct = 0, curL = 0, curR = -1;
  for (const qi of order) {
    const [l, r] = queries[qi];
    while (curR < r) if (++cnt[comp[++curR]] === 1) distinct++;
    while (curL > l) if (++cnt[comp[--curL]] === 1) distinct++;
    while (curR > r) if (--cnt[comp[curR--]] === 0) distinct--;
    while (curL < l) if (--cnt[comp[curL++]] === 0) distinct--;
    ans[qi] = distinct;
  }
  return ans;
}

function assert(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }
const eq = (x: number[], y: number[]) => x.length === y.length && x.every((v, i) => v === y[i]);
const gcd = (x: number, y: number): number => (y === 0 ? x : gcd(y, x % y));

const a = [5, 2, 4, 7, 1, 3, 6, 8];
const mn = new SparseTable(a, Math.min);
assert(eq([mn.query(0, 7), mn.query(1, 3), mn.query(5, 7), mn.query(2, 6), mn.query(3, 3)], [1, 2, 3, 1, 7]), "min");
const mx = new SparseTable(a, Math.max);
assert(mx.query(0, 3) === 7 && mx.query(4, 7) === 8, "max");
const g = new SparseTable([12, 18, 24, 36, 9], gcd);
assert(eq([g.query(0, 3), g.query(3, 4), g.query(0, 4)], [6, 9, 3]), "gcd");
const sm = new SparseTable(a, (x, y) => x + y);
assert(eq([sm.fold(2, 5), sm.fold(1, 6), sm.fold(0, 6)], [15, 23, 28]), "sum");

const sq = new SqrtSum(a);
assert(eq(sq.blocks, [11, 11, 14]) && sq.query(1, 6) === 23, "sqrt 1");
sq.set(4, 10);
assert(eq(sq.blocks, [11, 20, 14]) && sq.query(3, 5) === 20 && sq.query(0, 7) === 45, "sqrt 2");

const arr = [1, 2, 1, 3, 2, 2, 4, 1];
const qs: [number, number][] = [[0, 2], [1, 5], [0, 7], [5, 6], [3, 3], [2, 4]];
assert(eq(moDistinct(arr, qs), [2, 3, 4, 2, 1, 3]), "mo");
console.log("all tests pass");

Variant: sqrt decomposition with range add and range sum

Per-block lazy tags: a whole block takes the update in ; partial blocks are updated element by element. Verified against a brute-force array on random operations.

import random
from math import isqrt


class SqrtRangeAdd:
    def __init__(self, a: list[int]):
        n = len(a)
        self.b = max(1, isqrt(n))
        self.a = a[:]
        self.tag = [0] * ((n + self.b - 1) // self.b)      # pending add for the whole block
        self.sum = [0] * len(self.tag)
        for i, v in enumerate(a):
            self.sum[i // self.b] += v

    def _size(self, blk: int) -> int:
        return min(self.b, len(self.a) - blk * self.b)

    def add(self, l: int, r: int, x: int) -> None:
        b = self.b
        while l <= r and l % b != 0:
            self.a[l] += x; self.sum[l // b] += x; l += 1
        while l + b - 1 <= r:
            self.tag[l // b] += x; self.sum[l // b] += x * self._size(l // b); l += b
        while l <= r:
            self.a[l] += x; self.sum[l // b] += x; l += 1

    def query(self, l: int, r: int) -> int:
        b, s = self.b, 0
        while l <= r and l % b != 0:
            s += self.a[l] + self.tag[l // b]; l += 1
        while l + b - 1 <= r:
            s += self.sum[l // b]; l += b
        while l <= r:
            s += self.a[l] + self.tag[l // b]; l += 1
        return s


random.seed(7)
for _ in range(200):
    n = random.randint(1, 30)
    ref = [random.randint(-9, 9) for _ in range(n)]
    ds = SqrtRangeAdd(ref)
    for _ in range(40):
        l = random.randrange(n); r = random.randrange(l, n)
        if random.random() < 0.5:
            x = random.randint(-5, 5)
            ds.add(l, r, x)
            for i in range(l, r + 1):
                ref[i] += x
        else:
            assert ds.query(l, r) == sum(ref[l:r + 1])
print("range add ok")

Real-world uses

  • Suffix arrays and string processing. The longest common prefix of suffixes and is the minimum of the LCP array between their ranks. Libraries that build suffix arrays for full-text indexing and bioinformatics (read alignment, genome comparison) answer these with RMQ structures; Fischer and Heun's succinct RMQ was motivated by exactly this setting, where is billions of characters and words is unaffordable. See String Algorithms.
  • LCA in trees. The Euler-tour reduction turns lowest common ancestor into RMQ over depths. Phylogenetics tools, XML/DOM query engines (nearest common ancestor of two nodes) and compilers (dominator-tree queries) all need LCA; the reduction is the subject of LCA, Binary Lifting & Euler Tour.
  • Data skipping in columnar storage. Parquet stores min/max statistics per row group and per page; ORC keeps a row index with min/max for every 10,000 rows by default; ClickHouse has a minmax data-skipping index over granules. A range predicate such as WHERE ts BETWEEN a AND b reads a block summary first and skips blocks whose [min, max] cannot match. That is sqrt-style block decomposition applied to disk I/O: per-block summaries let the engine skip whole blocks and read only the partial ones. The idea goes back at least to Moerkotte's "Small Materialized Aggregates" (VLDB 1998). See Storage Engines, Indexing Deep Dive and Query Planning & Optimization.
  • Mo's algorithm is mostly a contest technique; its real-world cousin is reordering a batch of offline requests to improve locality (sorting I/O requests by position, the elevator algorithm in disk scheduling — see OS Algorithms). The common thread is that the cost of a request depends on the previous one, so the order matters.

Pitfalls & edge cases

  • Using the O(1) query for a non-idempotent operation. Sum, XOR and product give wrong answers with overlapping pieces, silently. Use fold (disjoint pieces) or prefix sums.
  • Floating-point log. int(math.log2(L)) can be off by one for large due to rounding. Use integer bit operations or a precomputed lg table.
  • Row length. Level has valid starts. Allocating per row and reading past the valid ones reads garbage (zeros, which then win every min query).
  • Number of levels. You need levels , i.e. n.bit_length() levels. An off-by-one here fails only on queries spanning nearly the whole array.
  • Memory. , 21 levels of 64-bit values is 168 MB. Use 32-bit values or store indices if the values are large objects.
  • Returning the position of the minimum. Store indices and compare a[i]; break ties consistently (leftmost) or the answer changes depending on which piece wins.
  • Sqrt block size of zero. isqrt(0) = 0; division by zero on an empty array. Clamp to at least 1.
  • Last block shorter. With range-add tags, the last block may have fewer than elements; sum += x * B is wrong for it.
  • Mo's: window order. Shrinking before extending can drive counts negative. Extend first.
  • Mo's: answers in the wrong order. Store ans[original index], not in processing order.
  • Mo's: forgetting coordinate compression. Values up to cannot index a count array; compress first, or use a hash map and accept the constant factor.
  • Mo's: wrong block size when . With , and , the right-pointer term is moves; cuts it to , and the left-pointer term is also . Tune .
  • Mo's in Python. interpreted pointer moves take minutes. Use PyPy, or vectorise, or pick the Fenwick sweep when the problem allows it.
  • Integer overflow in sums. Block sums of values up to need 64-bit integers.

Variations

Disjoint sparse table (runnable)

Any associative operation in per query — here sum, which the ordinary sparse table cannot do in . Pads to a power of two; level stores, for each block of size , suffix aggregates leftward from the midpoint and prefix aggregates rightward.

import random


class DisjointSparseTable:
    def __init__(self, a: list[int], op, identity: int):
        self.op, self.id = op, identity
        size = 1
        while size < max(2, len(a)):
            size *= 2
        self.levels = size.bit_length() - 1
        arr = a + [identity] * (size - len(a))
        self.arr = arr
        self.t = [[identity] * size for _ in range(self.levels)]
        for h in range(self.levels):
            half = 1 << h
            for mid in range(half, size, 2 * half):
                acc = identity
                for i in range(mid - 1, mid - half - 1, -1):    # suffixes ending at mid - 1
                    acc = op(arr[i], acc)
                    self.t[h][i] = acc
                acc = identity
                for j in range(mid, mid + half):                 # prefixes starting at mid
                    acc = op(acc, arr[j])
                    self.t[h][j] = acc

    def query(self, l: int, r: int) -> int:
        if l == r:
            return self.arr[l]
        h = (l ^ r).bit_length() - 1
        return self.op(self.t[h][l], self.t[h][r])


random.seed(3)
for _ in range(100):
    n = random.randint(1, 40)
    a = [random.randint(-50, 50) for _ in range(n)]
    dst = DisjointSparseTable(a, lambda x, y: x + y, 0)
    for _ in range(50):
        l = random.randrange(n); r = random.randrange(l, n)
        assert dst.query(l, r) == sum(a[l:r + 1])
print("disjoint sparse table ok")
  • Sparse table on a tree (binary lifting): , the -th ancestor of , is a sparse table over root-ward paths, and the same doubling recurrence builds it. Path minima are stored alongside. That is the next lesson, LCA, Binary Lifting & Euler Tour.
  • Sqrt decomposition on the value domain: split values into buckets with counts, giving insert and "k-th smallest". Combined with Mo's algorithm (which makes cheap inserts and only queries), this answers "k-th smallest in a range" or "mex of a range" offline without a log factor.
  • Segment tree versus everything here: see the comparison below.

When each structure wins

NeedBest choiceWhy
static range min/max/gcd, sparse table query, trivial code
static range sum/xorprefix sums memory, query
static range product mod or matrix productdisjoint sparse table for any associative op
point update + range query, mergeable summarysegment tree or Fenwick tree both
range update + range query, composable lazy tagsegment tree with lazy propagation both
summary that cannot be merged in (sorted block, pointers)sqrt decompositiononly needs "rebuild a block"
offline, answer maintainable by add/remove, not mergeableMo's algorithm, no merge needed
offline distinct countoffline Fenwick sweep
online distinct countpersistent segment tree per query
memory below wordsFischer–Heun succinct RMQ, block summaries on disk bits

Practice ladder

Each problem is described in my own words. Solutions are Python and are run as part of this page's checks, against brute force on random inputs rather than the official samples.

1. Static Range Minimum Queries (CSES 1647) — Easy. Fixed array, many range minima. Teaches the sparse table itself.

Hint

Build , then answer each query with two overlapping pieces of length .

Solution
import random


def solve(a: list[int], queries: list[tuple[int, int]]) -> list[int]:
    n = len(a)
    st = [a[:]]
    k = 1
    while (1 << k) <= n:
        p, h = st[-1], 1 << (k - 1)
        st.append([min(p[i], p[i + h]) for i in range(n - (1 << k) + 1)])
        k += 1
    out = []
    for l, r in queries:                      # 1-indexed, inclusive, as in CSES
        l -= 1; r -= 1
        k = (r - l + 1).bit_length() - 1
        out.append(min(st[k][l], st[k][r - (1 << k) + 1]))
    return out


random.seed(1)
for _ in range(100):
    a = [random.randint(1, 100) for _ in range(random.randint(1, 30))]
    qs = [tuple(sorted((random.randint(1, len(a)), random.randint(1, len(a))))) for _ in range(20)]
    assert solve(a, qs) == [min(a[l - 1:r]) for l, r in qs]
print("ok")

time, memory.

2. Range Sum Query - Mutable (LeetCode 307) — Medium. Point assignments and range sums. Teaches sqrt decomposition as the simplest structure that passes (a Fenwick tree is the other natural choice).

Hint

The SqrtSum class above is a complete solution.

3. Dynamic Range Minimum Queries (CSES 1649) — Easy/Medium. Like problem 1 but with point updates. Teaches why the sparse table dies with updates and how block minima recover.

Hint

Block minima with ; after a point update, recompute the one block's minimum in . A segment tree is the faster alternative.

4. Range Frequency Queries (LeetCode 2080) — Medium. Count occurrences of a value in a range. Teaches the alternative to block structures: per-value sorted position lists plus binary search.

Hint

Store, for each value, the sorted list of its indices; the count in is bisect_right(r) - bisect_left(l).

5. Iva & Pav (Codeforces 1878E) — Medium. For each query , find the largest with . Teaches AND as an idempotent operation and binary search over a monotone range function.

Hint

Range AND only loses bits as grows, so it is non-increasing in . Binary search , evaluating each candidate with an sparse-table query.

Solution
import random


def solve(a: list[int], queries: list[tuple[int, int]]) -> list[int]:
    n = len(a)
    st = [a[:]]
    k = 1
    while (1 << k) <= n:
        p, h = st[-1], 1 << (k - 1)
        st.append([p[i] & p[i + h] for i in range(n - (1 << k) + 1)])
        k += 1

    def and_range(l: int, r: int) -> int:
        k = (r - l + 1).bit_length() - 1
        return st[k][l] & st[k][r - (1 << k) + 1]

    out = []
    for l, k in queries:                       # l is 1-indexed; answer 1-indexed or -1
        l -= 1
        if a[l] < k:
            out.append(-1)
            continue
        lo, hi = l, n - 1                      # invariant: and_range(l, lo) >= k
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if and_range(l, mid) >= k:
                lo = mid
            else:
                hi = mid - 1
        out.append(lo + 1)
    return out


def brute(a, queries):
    out = []
    for l, k in queries:
        best, acc = -1, (1 << 30) - 1
        for r in range(l - 1, len(a)):
            acc &= a[r]
            if acc >= k:
                best = r + 1
        out.append(best)
    return out


random.seed(2)
for _ in range(200):
    a = [random.randint(1, 63) for _ in range(random.randint(1, 20))]
    qs = [(random.randint(1, len(a)), random.randint(1, 63)) for _ in range(15)]
    assert solve(a, qs) == brute(a, qs)
print("ok")

.

6. Pair of Numbers (Codeforces 359D) — Medium. Find the longest segments containing an element that divides every element of the segment. Teaches combining two sparse tables (gcd and min) and binary search on the answer length.

Hint

A segment qualifies iff its gcd equals its minimum. If some length works then every shorter length works (shrink around the dividing element), so binary search the length.

Solution
import random
from math import gcd


def build(a, op):
    st = [a[:]]
    k = 1
    while (1 << k) <= len(a):
        p, h = st[-1], 1 << (k - 1)
        st.append([op(p[i], p[i + h]) for i in range(len(a) - (1 << k) + 1)])
        k += 1
    return st


def q(st, op, l, r):
    k = (r - l + 1).bit_length() - 1
    return op(st[k][l], st[k][r - (1 << k) + 1])


def solve(a: list[int]) -> tuple[int, list[int]]:
    n = len(a)
    g, m = build(a, gcd), build(a, min)

    def starts(length: int) -> list[int]:
        return [l for l in range(n - length + 1) if q(g, gcd, l, l + length - 1) == q(m, min, l, l + length - 1)]

    lo, hi = 1, n                               # length 1 always works
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if starts(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo - 1, [l + 1 for l in starts(lo)]  # (r - l, 1-indexed starts)


def brute(a):
    n, best, ls = len(a), -1, []
    for l in range(n):
        for r in range(l, n):
            seg = a[l:r + 1]
            if any(all(x % d == 0 for x in seg) for d in seg):
                if r - l > best:
                    best, ls = r - l, [l + 1]
                elif r - l == best:
                    ls.append(l + 1)
    return best, ls


random.seed(5)
for _ in range(200):
    a = [random.choice([1, 2, 3, 4, 6, 8, 9, 12]) for _ in range(random.randint(1, 12))]
    assert solve(a) == brute(a)
print("ok")

for the tables plus per binary-search step: total.

7. CGCDSSQ (Codeforces 475D) — Medium/Hard. Count subarrays whose gcd equals each queried value. Teaches the "at most distinct gcds per left end" fact; a sparse table plus binary search finds where each gcd value changes.

Hint

Fix ; as grows, only changes when it drops to a proper divisor, at most times. Binary search each change point with the gcd sparse table and add the run length to a map keyed by gcd.

8. Holes (Codeforces 13E) — Hard. Holes push a ball forward by their power; powers change; report where the ball leaves and after how many jumps. Teaches sqrt decomposition on pointers.

Hint

For each hole store where the ball first lands outside its block, how many jumps that takes, and the last hole visited inside the block. An update rebuilds only its block (right to left). A query hops block by block.

Solution
import random
from math import isqrt


class Holes:
    def __init__(self, power: list[int]):
        self.n, self.p = len(power), power[:]
        self.b = max(1, isqrt(self.n))
        self.nxt = [0] * self.n
        self.cnt = [0] * self.n
        self.last = [0] * self.n
        for blk in range(0, self.n, self.b):
            self._rebuild(blk // self.b)

    def _rebuild(self, blk: int) -> None:
        lo, hi = blk * self.b, min(self.n, (blk + 1) * self.b)
        for i in range(hi - 1, lo - 1, -1):
            j = i + self.p[i]
            if j >= hi:                          # leaves the block (or the row) in one jump
                self.nxt[i], self.cnt[i], self.last[i] = j, 1, i
            else:
                self.nxt[i], self.cnt[i], self.last[i] = self.nxt[j], self.cnt[j] + 1, self.last[j]

    def set(self, i: int, v: int) -> None:
        self.p[i] = v
        self._rebuild(i // self.b)

    def throw(self, i: int) -> tuple[int, int]:
        jumps, last = 0, i
        while i < self.n:
            jumps += self.cnt[i]
            last = self.last[i]
            i = self.nxt[i]
        return last, jumps                       # 0-indexed last hole, jump count


def brute_throw(p, i):
    jumps, last = 0, i
    while i < len(p):
        last, i, jumps = i, i + p[i], jumps + 1
    return last, jumps


random.seed(4)
for _ in range(200):
    n = random.randint(1, 25)
    p = [random.randint(1, n) for _ in range(n)]
    h = Holes(p)
    for _ in range(30):
        if random.random() < 0.4:
            i, v = random.randrange(n), random.randint(1, n)
            h.set(i, v); p[i] = v
        else:
            i = random.randrange(n)
            assert h.throw(i) == brute_throw(p, i)
print("ok")

Each update ; each query visits at most blocks: .

9. Distinct Values Queries (CSES 1734) — Medium. Number of distinct values in each range. Teaches Mo's algorithm (and the offline Fenwick sweep, which is faster).

Hint

Either mo_distinct from the implementation, or sort queries by and keep a 1 in a Fenwick tree at the last occurrence of each value.

Solution
import random


def distinct_offline(arr: list[int], queries: list[tuple[int, int]]) -> list[int]:
    n = len(arr)
    bit = [0] * (n + 1)

    def add(i: int, d: int) -> None:
        i += 1
        while i <= n:
            bit[i] += d
            i += i & -i

    def pref(i: int) -> int:                     # sum of marks in [0, i]
        i += 1
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    order = sorted(range(len(queries)), key=lambda qi: queries[qi][1])
    last: dict[int, int] = {}
    ans = [0] * len(queries)
    r_done = -1
    for qi in order:
        l, r = queries[qi]
        while r_done < r:
            r_done += 1
            v = arr[r_done]
            if v in last:
                add(last[v], -1)
            last[v] = r_done
            add(r_done, 1)
        ans[qi] = pref(r) - (pref(l - 1) if l else 0)
    return ans


random.seed(6)
for _ in range(200):
    arr = [random.randint(1, 6) for _ in range(random.randint(1, 25))]
    qs = [tuple(sorted((random.randrange(len(arr)), random.randrange(len(arr))))) for _ in range(20)]
    assert distinct_offline(arr, qs) == [len(set(arr[l:r + 1])) for l, r in qs]
print("ok")

.

10. DQUERY (SPOJ) — Medium. The original "distinct elements in a range" benchmark for Mo's algorithm. Teaches implementing Mo's with tight constants (arrays, not hash maps).

Hint

Values are small enough to index a count array directly; use the odd-even order and .

11. Little Elephant and Array (Codeforces 220B) — Medium/Hard. Count values that occur exactly times in a range. Teaches Mo's with a condition on counts.

Hint

Only values can qualify. In add, if the count of becomes , increment the answer; if it moves from to , decrement. Mirror in remove.

12. Powerful array (Codeforces 86D) — Hard. Sum over values of in a range. Teaches Mo's with a non-trivial delta: adding one changes the answer by .

Hint

When the count of goes from to , the answer increases by . Use 64-bit integers.

13. Online Majority Element In Subarray (LeetCode 1157) — Hard. Online queries for a value occurring at least a threshold number of times. Teaches a heavy/light (sqrt) split on value frequencies, or randomisation plus position lists.

Hint

The threshold exceeds half the subarray length, so a uniformly random position in the subarray holds the answer with probability above 1/2. Try about 20 random positions and verify each candidate's count by binary search on its sorted list of positions; the failure probability is below . A deterministic alternative: values with more than occurrences (at most of them) get prefix-count arrays, and subarrays shorter than are scanned directly (Boyer–Moore voting).

14. Machine Learning (Codeforces 940F) — Expert. Range queries for the mex of the multiset of counts, with point updates in between. Teaches Mo's with updates () and the observation that the mex of counts is at most about , so it can be found by scanning.

Hint

Queries are points . Sort by . Keep cnt[value] and cntOfCnt[c]; the mex scan over cntOfCnt stops within because counts all present need elements.

Common mistakes & interview follow-ups

"Why not just use a segment tree?" For static idempotent queries with , the sparse table is faster ( versus ) and shorter. For anything with updates, use the segment tree. Be able to state both sides.

"What does idempotent mean and why does it matter here?" . The query covers the range with two overlapping pieces; idempotence (plus associativity) makes the overlap harmless. Give the XOR counterexample: on [1, 1, 1] the query uses pieces and , each with XOR 0, so it returns 0, but the true XOR is 1.

"Can you reduce memory?" Store only rows of decreasing length (saves little), use 32-bit types, or the block scheme: sparse table over block minima of size plus in-block scans gives memory with query, or with the Fischer–Heun lookup tables.

"What if the queries come online?" Mo's algorithm is out. For distinct counts use a persistent segment tree. For general add/remove-maintainable statistics online, there is often no good answer; sqrt decomposition with precomputed answers between block boundaries ( memory) is one route.

"Prove the Mo's bound." is monotone within a block: per block, blocks. moves at most per query. Total , optimised at .

"Pick the block size for sqrt decomposition when updates are more frequent than queries." If updates cost (rebuild a block) and queries , and updates are times more frequent, minimise : .

Common mistakes: float log2; wrong number of levels; XOR or sum with the overlapping query; Mo's answers stored in sorted order; shrinking the window before extending it; B = sqrt(n) when ; integer overflow in block sums.

Quick quiz

  1. For a = [5, 2, 4, 7, 1, 3, 6, 8], which two table entries answer min(2, 6) and what are they?
Answer

Length 5, so . Pieces (indices 2..5) and (indices 3..6), both equal to 1. Answer 1.

  1. Why does the overlapping query not need the operation to be commutative?
Answer

The overlap is a suffix of the left piece and a prefix of the right piece, so the combination is using only associativity and idempotence. The order of the elements is preserved.

  1. A sqrt decomposition uses on . Roughly how many steps does a full-range query take, and what would you choose instead?
Answer

At most partial elements plus blocks, about steps. gives at most about .

  1. In Mo's algorithm with and , compare the -pointer bound for and .
Answer

moves . With : . With : , while the term balances it. Total about instead of about .

  1. Name an operation for which the disjoint sparse table gives queries but the ordinary sparse table does not.
Answer

Sum (or XOR, or product modulo a prime, or matrix product, or function composition): associative but not idempotent.

Further reading / sources

  • cp-algorithms: Sparse Table, Sqrt Decomposition (includes Mo's algorithm), Sqrt Tree. The disjoint sparse table has no cp-algorithms page at the time of writing; it is documented in competitive-programming blog posts and contest libraries, and the version on this page is verified against brute force.
  • M. A. Bender & M. Farach-Colton, "The LCA Problem Revisited", LATIN 2000, LNCS 1776, pp. 88–94. DOI 10.1007/10719839_9.
  • J. Fischer & V. Heun, "Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays", SIAM Journal on Computing 40(2):465–492, 2011. DOI 10.1137/090779759.
  • H. N. Gabow, J. L. Bentley & R. E. Tarjan, "Scaling and related techniques for geometry problems", STOC 1984, pp. 135–143 — the RMQ ↔ LCA reduction via Cartesian trees.
  • O. Berkman & U. Vishkin, "Recursive star-tree parallel data structure", SIAM Journal on Computing 22(2):221–242, 1993 — power-of-two precomputation in parallel RMQ/LCA.
  • G. Moerkotte, "Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing", VLDB 1998 — block min/max summaries for skipping.
  • Codeforces blog by gepardo, "An alternative sorting order for Mo's algorithm" (2017) — the Hilbert-curve ordering; and the Codeforces/CP-algorithms treatments of Mo's with updates.
  • A. Laaksonen, Competitive Programmer's Handbook, chapter 9 (range queries: sparse table) and chapter 27 (square root algorithms, including Mo's algorithm).
  • Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., Chapter 16 (amortized analysis, for reasoning about Mo's pointer movement) — RMQ itself appears only in the problems.

Prev: Fenwick Trees (Binary Indexed Trees) · Next: LCA, Binary Lifting & Euler Tour

Related: Module 3 — Trees · Segment Trees in Depth · Prefix Sums & Difference Arrays · Monotonic Stack & Monotonic Deque · Advanced Data Structures · String Algorithms · Heavy-Light & Centroid Decomposition · DSA: Zero to Mastery