Algo: Mo's Algorithm for Offline Range Queries

Mo's algorithm is a cornerstone technique for efficiently answering multiple range queries when all queries are known beforehand and no updates occur to the underlying array. By cleverly reordering queries using square-root decomposition, it minimizes the total movement of query pointers, achieving a time complexity of $O(n\sqrt{n})$. This makes it exceptionally powerful for competitive programming and data analysis tasks involving statistical queries over static data sets.

Foundations: Offline Queries and Square-Root Decomposition

Offline range queries refer to a set of queries, such as "find the frequency of a number in subarray [L, R]," where all queries are provided in advance. You are free to answer them in any order to optimize total computation time. The foundational idea behind Mo's algorithm is square-root decomposition, which involves dividing the array of size $n$ into blocks of approximately $\sqrt{n}$ size. This blocking strategy balances the workload: operations within a block are cheap, and transitions between blocks are controlled. For range queries, this decomposition allows you to process queries by grouping those with similar starting points, thereby reducing redundant pointer movements across the array. Think of it like a postal worker sorting deliveries by neighborhood blocks to minimize travel time rather than following the exact order of requests.

The Core of Mo's Algorithm: Query Sorting and Processing

The algorithm works by maintaining a current range [curL, curR] and two pointers that you move to adjust this range for each query. First, you sort all queries based on the block index of their left endpoint $L$. The block index is calculated as $L/\sqrt{n}$ (using integer division). Within the same block, queries are sorted by their right endpoint $R$ in ascending order. This specific ordering is crucial: it ensures that the left pointer moves only within its block most of the time, while the right pointer moves monotonically across queries. You initialize curL to 0 and curR to -1 (an empty range), then process each sorted query by expanding or shrinking the current range using add and remove functions. These functions update a data structure, like a frequency array, in $O(1)$ time as pointers move.

Complexity Analysis: Achieving $O(n\sqrt{n})$

The efficiency stems from bounding total pointer movements. Since queries are sorted by blocks of size $\sqrt{n}$, the left pointer moves at most $\sqrt{n}$ times per query within a block, leading to $O(q\sqrt{n})$ movements total, where $q$ is the number of queries. The right pointer moves monotonically within each block; across all blocks, it moves at most $O(n\sqrt{n})$ times because there are $\sqrt{n}$ blocks and the right pointer traverses the entire array in the worst case per block. Therefore, the overall time complexity is $O((n+q)\sqrt{n})$, which simplifies to $O(n\sqrt{n})$ when $q$ is proportional to $n$. This complexity is derived directly from the square-root decomposition basis, balancing block-wise processing.

Practical Implementation: Range Frequency and Distinct Elements

To implement Mo's algorithm, you need to define add(pos) and remove(pos) functions that update your answer when a pointer includes or excludes an element at position pos. For a range frequency query—counting how many times a value $k$ appears in [L, R]—you maintain a frequency array freq[] and a variable count. When add(pos) is called, you increment freq[array[pos]] and if freq[array[pos]] equals 1 (or the target), update count. Remove(pos) does the opposite. Process each query by moving pointers and recording the answer.

For distinct element queries, the setup is similar: maintain freq[] and a distinctcount. In add(pos), if freq[array[pos]] is 0, increment distinctcount; then increment freq. In remove(pos), decrement freq and if it becomes 0, decrement distinct_count. Here's a step-by-step snippet of the sorting logic in Python-like pseudocode:

block_size = int(n**0.5)
queries.sort(key=lambda x: (x.L // block_size, x.R))

Then, iterate through queries, adjusting curL and curR with while loops that call add or remove.

When to Choose Mo's Algorithm Over Segment Trees

Mo's algorithm outperforms segment trees in specific scenarios. Segment trees are excellent for online queries with updates, achieving $O(\log n)$ per query or update. However, Mo's algorithm is preferable when you have a static array and many offline range queries without updates. For problems like range frequency, mode, or distinct element counts, Mo's algorithm often runs faster in practice due to lower constant factors and the $O(n\sqrt{n})$ complexity being efficient for $n$ up to around $10^5$. Segment trees might require more complex node structures for such queries, leading to higher overhead. Choose Mo's when updates are absent and queries involve aggregate functions that can be updated incrementally with pointer movements.

Common Pitfalls

1. Incorrect Sorting Order: A common mistake is sorting queries only by left endpoint without considering blocks, or sorting right endpoints in descending order within a block. This disrupts the monotonic movement of the right pointer, increasing complexity to $O(n^2)$. Correction: Always sort by (leftblock, rightendpoint) with right in ascending order.

1. Inefficient Add/Remove Operations: Implementing add and remove functions with more than $O(1)$ complexity, such as using binary search trees unnecessarily, can degrade performance. Correction: Use simple arrays or hash maps for frequency counts to ensure constant-time updates.

1. Applying Mo's to Problems with Updates: Mo's algorithm does not support updates to the array; attempting to adapt it for dynamic arrays often leads to incorrect results or high complexity. Correction: For problems with updates, use data structures like segment trees or Binary Indexed Trees instead.

1. Misjudging Block Size: Using a fixed block size like 100 instead of $\sqrt{n}$ can lead to suboptimal performance. Correction: Calculate block size as $\sqrt{n}$ dynamically based on input size to balance pointer movements.

Summary

• Mo's algorithm answers offline range queries by sorting queries based on the block of their left endpoint, minimizing total pointer movement to $O(n\sqrt{n})$.
• It relies on square-root decomposition, dividing the array into blocks of size $\sqrt{n}$ to balance processing costs.
• Implementation requires defining efficient add and remove functions for pointer adjustments, suitable for queries like range frequency and distinct element counts.
• The algorithm outperforms segment trees in scenarios with no updates and many queries, thanks to its incremental update strategy and lower constant factors.
• Key pitfalls include incorrect query sorting, slow update functions, and misapplying the algorithm to problems with updates.
• Mastering Mo's algorithm equips you with a powerful tool for static data analysis in competitive programming and engineering applications.