Sqrt Decomposition and Mo's Algorithm

---

The Idea: Divide the Array into Blocks

Sqrt decomposition is one of the simplest yet most powerful techniques for range queries. The idea is elegant:

1. Divide the array of size n into blocks of size sqrt(n).
2. Precompute the answer (sum, min, max, etc.) for each complete block.
3. For a range query, combine the precomputed answers for full blocks and manually process the partial blocks at the edges.

Since there are sqrt(n) blocks and each block has sqrt(n) elements, both the number of full blocks and the size of partial blocks are bounded by sqrt(n). This gives us O(sqrt(n)) per query.

---

Range Sum Queries with Point Updates

Building the Block Array

import math

class SqrtDecomposition:
    """Sqrt decomposition for range sum queries with point updates."""
    
    def __init__(self, arr):
        self.arr = arr[:]  # Copy the array
        self.n = len(arr)
        self.block_size = max(1, int(math.isqrt(self.n)))
        self.num_blocks = (self.n + self.block_size - 1) // self.block_size
        
        # Compute block sums
        self.block_sum = [0] * self.num_blocks
        for i in range(self.n):
            self.block_sum[i // self.block_size] += arr[i]
    
    def update(self, idx, new_val):
        """Update arr[idx] to new_val. O(1)."""
        block_idx = idx // self.block_size
        self.block_sum[block_idx] += new_val - self.arr[idx]
        self.arr[idx] = new_val
    
    def query(self, l, r):
        """Return sum(arr[l..r]). O(sqrt(n))."""
        total = 0
        
        # Block indices for l and r
        block_l = l // self.block_size
        block_r = r // self.block_size
        
        if block_l == block_r:
            # Same block: just iterate
            for i in range(l, r + 1):
                total += self.arr[i]
        else:
            # Left partial block
            left_block_end = (block_l + 1) * self.block_size - 1
            for i in range(l, left_block_end + 1):
                total += self.arr[i]
            
            # Full blocks in between
            for b in range(block_l + 1, block_r):
                total += self.block_sum[b]
            
            # Right partial block
            right_block_start = block_r * self.block_size
            for i in range(right_block_start, r + 1):
                total += self.arr[i]
        
        return total


# Example
arr = [2, 5, 3, 7, 1, 4, 8, 6, 9]
sd = SqrtDecomposition(arr)

print(f"sum(0, 8) = {sd.query(0, 8)}")  # 45
print(f"sum(1, 7) = {sd.query(1, 7)}")  # 34
print(f"sum(3, 5) = {sd.query(3, 5)}")  # 12

# Update: change arr[4] from 1 to 10
sd.update(4, 10)
print(f"After update, sum(3, 5) = {sd.query(3, 5)}")  # 21

Why sqrt(n)?

The choice of sqrt(n) as the block size minimizes the worst-case query time. With block size B:

• Number of full blocks scanned: at most n/B
• Partial elements scanned: at most 2B
• Total: n/B + 2B

Taking the derivative and setting it to zero: B = sqrt(n) minimizes n/B + 2B = 3*sqrt(n).

---

Range Min Query with Sqrt Decomposition

class SqrtDecompositionMin:
    """Sqrt decomposition for range minimum queries."""
    
    def __init__(self, arr):
        self.arr = arr[:]
        self.n = len(arr)
        self.block_size = max(1, int(math.isqrt(self.n)))
        self.num_blocks = (self.n + self.block_size - 1) // self.block_size
        
        self.block_min = [float('inf')] * self.num_blocks
        for i in range(self.n):
            b = i // self.block_size
            self.block_min[b] = min(self.block_min[b], arr[i])
    
    def update(self, idx, new_val):
        """Update arr[idx]. O(sqrt(n)) -- must recompute block min."""
        self.arr[idx] = new_val
        b = idx // self.block_size
        
        # Recompute this block's min
        start = b * self.block_size
        end = min(start + self.block_size, self.n)
        self.block_min[b] = min(self.arr[start:end])
    
    def query(self, l, r):
        """Return min(arr[l..r]). O(sqrt(n))."""
        result = float('inf')
        block_l = l // self.block_size
        block_r = r // self.block_size
        
        if block_l == block_r:
            for i in range(l, r + 1):
                result = min(result, self.arr[i])
        else:
            # Left partial
            for i in range(l, (block_l + 1) * self.block_size):
                result = min(result, self.arr[i])
            
            # Full blocks
            for b in range(block_l + 1, block_r):
                result = min(result, self.block_min[b])
            
            # Right partial
            for i in range(block_r * self.block_size, r + 1):
                result = min(result, self.arr[i])
        
        return result


arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sdm = SqrtDecompositionMin(arr)
print(f"min(0, 10) = {sdm.query(0, 10)}")  # 1
print(f"min(4, 8) = {sdm.query(4, 8)}")    # 2

Note: For min queries, updates are O(sqrt(n)) because we must recompute the block’s minimum. For sum queries, updates are O(1).

---

Range Updates with Sqrt Decomposition (Lazy Propagation)

Sqrt decomposition can also handle range updates (add a value to all elements in a range) using a “lazy” approach:

class SqrtDecompositionRangeUpdate:
    """Supports range add and range sum queries."""
    
    def __init__(self, arr):
        self.arr = arr[:]
        self.n = len(arr)
        self.block_size = max(1, int(math.isqrt(self.n)))
        self.num_blocks = (self.n + self.block_size - 1) // self.block_size
        
        self.block_sum = [0] * self.num_blocks
        self.lazy = [0] * self.num_blocks  # Pending add for entire block
        
        for i in range(self.n):
            self.block_sum[i // self.block_size] += arr[i]
    
    def range_add(self, l, r, val):
        """Add val to all elements in arr[l..r]. O(sqrt(n))."""
        block_l = l // self.block_size
        block_r = r // self.block_size
        
        if block_l == block_r:
            for i in range(l, r + 1):
                self.arr[i] += val
                self.block_sum[block_l] += val
        else:
            # Left partial
            for i in range(l, (block_l + 1) * self.block_size):
                self.arr[i] += val
                self.block_sum[block_l] += val
            
            # Full blocks: use lazy
            for b in range(block_l + 1, block_r):
                self.lazy[b] += val
                self.block_sum[b] += val * self.block_size
            
            # Right partial
            for i in range(block_r * self.block_size, r + 1):
                self.arr[i] += val
                self.block_sum[block_r] += val
    
    def query(self, l, r):
        """Range sum query. O(sqrt(n))."""
        total = 0
        block_l = l // self.block_size
        block_r = r // self.block_size
        
        if block_l == block_r:
            for i in range(l, r + 1):
                total += self.arr[i] + self.lazy[block_l]
        else:
            for i in range(l, (block_l + 1) * self.block_size):
                total += self.arr[i] + self.lazy[block_l]
            
            for b in range(block_l + 1, block_r):
                total += self.block_sum[b]
            
            for i in range(block_r * self.block_size, r + 1):
                total += self.arr[i] + self.lazy[block_r]
        
        return total


arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
sd = SqrtDecompositionRangeUpdate(arr)
print(f"sum(0, 8) = {sd.query(0, 8)}")  # 45

sd.range_add(2, 6, 10)  # Add 10 to indices 2-6
print(f"After range_add, sum(0, 8) = {sd.query(0, 8)}")  # 95
print(f"sum(3, 5) = {sd.query(3, 5)}")  # 45

---

Mo’s Algorithm: Offline Range Queries

Mo’s algorithm is a technique for answering offline range queries (where you know all queries in advance) in O((n + q) * sqrt(n)) time. It sorts queries cleverly to minimize the total work of adding/removing elements from the current range.

The Key Insight

If we process queries in a specific order, moving the left and right pointers of our “current range” requires only O(sqrt(n)) amortized moves per query.

Sorting strategy: Sort queries by (l // block_size, r). Within the same block of l, queries are sorted by r, so the right pointer moves monotonically.

Implementation

import math
from collections import defaultdict

def mos_algorithm(arr, queries):
    """
    Answer offline range queries using Mo's algorithm.
    
    Each query (l, r) asks: how many distinct elements in arr[l..r]?
    
    Returns answers in the original query order.
    """
    n = len(arr)
    q = len(queries)
    block_size = max(1, int(math.isqrt(n)))
    
    # Sort queries by (l // block_size, r)
    # Also store original index to restore order
    sorted_queries = sorted(
        enumerate(queries),
        key=lambda x: (x[1][0] // block_size, 
                       x[1][1] if (x[1][0] // block_size) % 2 == 0 
                       else -x[1][1])
    )
    
    # Current window state
    freq = defaultdict(int)
    distinct_count = 0
    cur_l, cur_r = 0, -1
    
    answers = [0] * q
    
    def add(idx):
        nonlocal distinct_count
        freq[arr[idx]] += 1
        if freq[arr[idx]] == 1:
            distinct_count += 1
    
    def remove(idx):
        nonlocal distinct_count
        freq[arr[idx]] -= 1
        if freq[arr[idx]] == 0:
            distinct_count -= 1
    
    for orig_idx, (l, r) in sorted_queries:
        # Expand/shrink window to [l, r]
        while cur_r < r:
            cur_r += 1
            add(cur_r)
        while cur_l > l:
            cur_l -= 1
            add(cur_l)
        while cur_r > r:
            remove(cur_r)
            cur_r -= 1
        while cur_l < l:
            remove(cur_l)
            cur_l += 1
        
        answers[orig_idx] = distinct_count
    
    return answers


# Example: count distinct elements in each range
arr = [1, 2, 1, 3, 2, 1, 4, 2, 3]
queries = [(0, 4), (1, 6), (2, 8), (0, 8), (3, 5)]

answers = mos_algorithm(arr, queries)
for i, (l, r) in enumerate(queries):
    print(f"Distinct in [{l}, {r}] = {answers[i]}")

Output:

Distinct in [0, 4] = 3
Distinct in [1, 6] = 4
Distinct in [2, 8] = 4
Distinct in [0, 8] = 4
Distinct in [3, 5] = 3

Mo’s Algorithm with Updates (Mo’s with Timestamps)

A variation handles queries with point updates interspersed. The idea adds a third dimension (time) and uses block size n^(2/3):

def mos_with_updates(arr, queries, updates):
    """
    Mo's algorithm supporting interleaved point updates.
    
    queries: list of (l, r, time) where time is the update count before this query
    updates: list of (idx, new_val, old_val)
    
    Block size: n^(2/3) for optimal complexity O(n^(5/3)).
    """
    n = len(arr)
    block_size = max(1, int(n ** (2/3)))
    
    sorted_queries = sorted(
        enumerate(queries),
        key=lambda x: (
            x[1][0] // block_size,
            x[1][1] // block_size,
            x[1][2]
        )
    )
    
    current_arr = arr[:]
    freq = defaultdict(int)
    distinct = 0
    cur_l, cur_r, cur_t = 0, -1, 0
    answers = [0] * len(queries)
    
    def add(idx):
        nonlocal distinct
        freq[current_arr[idx]] += 1
        if freq[current_arr[idx]] == 1:
            distinct += 1
    
    def remove(idx):
        nonlocal distinct
        freq[current_arr[idx]] -= 1
        if freq[current_arr[idx]] == 0:
            distinct -= 1
    
    def apply_update(t):
        idx, new_val, old_val = updates[t]
        if cur_l <= idx <= cur_r:
            remove(idx)
        current_arr[idx] = new_val
        if cur_l <= idx <= cur_r:
            add(idx)
    
    def undo_update(t):
        idx, new_val, old_val = updates[t]
        if cur_l <= idx <= cur_r:
            remove(idx)
        current_arr[idx] = old_val
        if cur_l <= idx <= cur_r:
            add(idx)
    
    for orig_idx, (l, r, t) in sorted_queries:
        while cur_t < t:
            apply_update(cur_t)
            cur_t += 1
        while cur_t > t:
            cur_t -= 1
            undo_update(cur_t)
        
        while cur_r < r:
            cur_r += 1
            add(cur_r)
        while cur_l > l:
            cur_l -= 1
            add(cur_l)
        while cur_r > r:
            remove(cur_r)
            cur_r -= 1
        while cur_l < l:
            remove(cur_l)
            cur_l += 1
        
        answers[orig_idx] = distinct
    
    return answers

---

Complexity Analysis

Technique	Build	Query	Point Update	Range Update
Sqrt Decomposition (sum)	O(n)	O(sqrt(n))	O(1)	O(sqrt(n))
Sqrt Decomposition (min)	O(n)	O(sqrt(n))	O(sqrt(n))	O(sqrt(n))
Mo’s Algorithm	O(q log q) sort	O((n+q) sqrt(n)) total	-	-
Mo’s with Updates	O(q log q) sort	O((n+q) n^(2/3)) total	Yes	-

---

When to Use Sqrt Decomposition

Advantages Over Segment Trees

• Simpler to implement — no recursive tree structure
• Cache-friendly — sequential memory access within blocks
• Flexible — handles complex queries that are hard to merge in segment trees
• Mo’s algorithm — enables offline queries that segment trees cannot easily handle

Disadvantages

• Slower queries: O(sqrt(n)) vs O(log n) for segment trees
• Not suitable for all operations: Some operations need the hierarchical structure of a tree

Decision Guide

• Need O(log n) queries with updates? Segment tree
• Static array with simple range queries? Sparse table (O(1)) or prefix sums
• Complex offline queries (distinct count, mode, etc.)? Mo’s algorithm
• Need something quick to implement in a contest? Sqrt decomposition

---

Practice Problems

1. Range Sum with Point Updates — Direct sqrt decomposition application.
2. DQUERY (SPOJ) — Count distinct elements in range. Classic Mo’s algorithm problem.
3. Powerful Array (CF 86D) — Sum of count^2 * value for each range. Mo’s algorithm.
4. XOR on Segments — Sqrt decomposition with lazy XOR propagation.
5. Mo’s Algorithm on Trees — Flatten the tree with Euler tour, then apply Mo’s on the resulting array.

---

Key Takeaways

• Sqrt decomposition divides an array into sqrt(n) blocks, giving O(sqrt(n)) per query and update.
• The block size sqrt(n) minimizes the worst-case cost of scanning full blocks plus partial edges.
• Mo’s algorithm sorts offline queries to minimize pointer movement, achieving O((n+q) sqrt(n)) total.
• Mo’s with timestamps extends the technique to handle updates at the cost of O(n^(5/3)) total.
• Sqrt decomposition is a versatile tool: simpler than segment trees, powerful enough for many contest problems.