{"title":"Mo's Algorithm","description":"","content":"You have an array of 100,000 elements and 100,000 queries, each asking \"how many distinct values are in the range [L, R]?\" A brute force scan per query gives O(n) each, totaling O(n * q) which is roughly 10^10 operations. That is far too slow. A segment tree could help for some query types, but maintaining distinct counts across arbitrary ranges is awkward to merge. Mo's Algorithm solves this class of problems in O((n + q) * sqrt(n)) using a beautifully simple idea: sort the queries in a clever order, then slide a window across the array, adding and removing one element at a time.\n\nIf you are comfortable with basic sorting and square root decomposition concepts, you are ready for this chapter. By the end, you will understand how Mo's Algorithm works, why its complexity is what it is, and how to implement it for a variety of offline range query problems.\n\n---\n\n# Why Mo's Algorithm Matters\n\nMo's Algorithm occupies a unique niche in the algorithmic toolkit. It is not the fastest approach for any single problem, but it is one of the most versatile techniques for offline range queries, problems where you receive all queries upfront and can answer them in any order.\n\n- **Competitive programming workhorse.** A large class of range query problems on Codeforces, AtCoder, and SPOJ have Mo's Algorithm as the intended or alternate solution. Learning it unlocks dozens of problems that would otherwise require complex persistent data structures.\n- **Elegant simplicity.** The entire idea boils down to sorting queries smartly and maintaining a sliding window. There is no segment tree to build, no merge function to design, no lazy propagation to debug. If you can write an `add` and a `remove` function, you can use Mo's.\n- **Offline query processing.** Many real interview and contest problems give you all queries at once. Mo's Algorithm teaches you to think about query ordering as an optimization lever, a mindset that transfers to other problems like offline LCA or batch processing.\n- **Pairs well with other techniques.** Mo's Algorithm can be extended with updates (Mo's with modifications), applied to trees (Mo's on trees via Euler tour), or combined with bitsets for frequency problems.\n\n---\n\n# The Core Idea\n\n### The Problem\n\nConsider an array `arr` of `n` elements and `q` queries, each of the form \"compute some aggregate over the subarray arr[L..R].\" The aggregate could be the count of distinct elements, the sum of element frequencies squared, the mode, or any decomposable statistic.\n\nThe naive approach processes each query independently by iterating from L to R, giving O(n) per query and O(n * q) total. For n = q = 100,000, that is 10^10 operations, which is far too slow.\n\nYou might think about prefix sums, but they only work for simple additive aggregates. For something like \"count of distinct elements,\" prefix sums fall apart because the distinct count of [L, R] is not simply `prefix[R] - prefix[L-1]`.\n\n### The Key Insight\n\nHere is the core observation: if you already know the answer for the range [L, R], you can compute the answer for [L, R+1] by just adding one element (arr[R+1]). Similarly, you can go from [L, R] to [L+1, R] by removing one element (arr[L]). Each transition costs O(1) if your `add` and `remove` operations are O(1).\n\nThe question becomes: in what order should you process the queries so that the total pointer movement is minimized?\n\nMo's answer is to divide the array into blocks of size sqrt(n), then sort queries by (block number of L, R). Within the same block, queries are sorted by R. This guarantees that:\n\n1. The left pointer never moves more than sqrt(n) between consecutive queries in the same block.\n2. The right pointer sweeps left-to-right within each block, moving at most n total per block.\n\nThe result is O((n + q) * sqrt(n)) total pointer movement across all queries.\n\n### The Analogy\n\nImagine you are a librarian cataloging books on a long shelf. A patron gives you a list of requests: \"count the unique titles between positions 10 and 50,\" \"between positions 12 and 48,\" and so on. If you handle requests in the order they arrive, you might jump from one end of the shelf to the other for every request.\n\nBut if you group the requests by which section of the shelf the left endpoint falls in, and within each section sort by the right endpoint, you minimize your walking. Within a section, your left hand barely moves (it stays within a small zone), and your right hand sweeps steadily in one direction. That is Mo's Algorithm: organizing work to minimize total movement.\n\n### Visual Overview\n\n\n```mermaid\nflowchart LR\n A[\"All Queries
(unsorted)\"]:::primary --> B[\"Sort by
Block(L), then R\"]:::orange\n B --> C[\"Process in
Sorted Order\"]:::teal\n C --> D[\"Slide Window
[curL, curR]\"]:::primary\n D --> E[\"add / remove
One Element\"]:::green\n E --> F[\"Store Answer
for Query\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# How It Works\n\n### Step 1: Choose the Block Size\n\nSet the block size `B = floor(sqrt(n))`. Each index `i` in the array belongs to block `i / B`. For an array of size 16, the block size is 4, and indices 0-3 are in block 0, indices 4-7 are in block 1, and so on.\n\n### Step 2: Sort the Queries\n\nEach query is a triple (L, R, original_index). Sort the queries using a comparator:\n\n1. **Primary key:** Block number of L, which is `L / B`.\n2. **Secondary key:** R value. For even-numbered blocks, sort R ascending. For odd-numbered blocks, sort R descending.\n\nThe alternating sort direction for R is a well-known optimization. Without it, when you transition from one block to the next, R might jump from a high value back to a low value, wasting O(n) movement. Alternating the direction means R sweeps forward in one block and backward in the next, keeping the transition smooth.\n\n\n```mermaid\nflowchart TD\n subgraph Block0[\"Block 0: indices 0-3\"]\n Q1[\"Q(1,7)\"]:::primary\n Q2[\"Q(2,5)\"]:::primary\n Q3[\"Q(3,9)\"]:::primary\n end\n\n subgraph Block1[\"Block 1: indices 4-7\"]\n Q4[\"Q(4,8)\"]:::orange\n Q5[\"Q(5,3)\"]:::orange\n Q6[\"Q(6,6)\"]:::orange\n end\n\n subgraph Sorted0[\"Block 0 sorted
(even: R ascending)\"]\n S1[\"Q(2,5)\"]:::teal\n S2[\"Q(1,7)\"]:::teal\n S3[\"Q(3,9)\"]:::teal\n end\n\n subgraph Sorted1[\"Block 1 sorted
(odd: R descending)\"]\n S4[\"Q(4,8)\"]:::green\n S5[\"Q(6,6)\"]:::green\n S6[\"Q(5,3)\"]:::green\n end\n\n Block0 --> Sorted0\n Block1 --> Sorted1\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Step 3: Process Queries with a Sliding Window\n\nMaintain a current window `[curL, curR]` that starts empty (for instance, curL = 0 and curR = -1). For each query (L, R) in sorted order:\n\n1. **Expand right:** While `curR < R`, increment curR and call `add(curR)`.\n2. **Shrink right:** While `curR > R`, call `remove(curR)` and decrement curR.\n3. **Expand left:** While `curL > L`, decrement curL and call `add(curL)`.\n4. **Shrink left:** While `curL < L`, call `remove(curL)` and increment curL.\n5. **Record the answer** for this query at its original index.\n\nThe order matters here. It is generally safer to expand the window before shrinking it, which avoids the window temporarily becoming invalid (where curL > curR).\n\n### Step 4: The add and remove Functions\n\nThese are problem-specific. For counting distinct elements in a range:\n\n- **add(index):** Increment the frequency count of `arr[index]`. If the frequency goes from 0 to 1, increment the distinct count.\n- **remove(index):** Decrement the frequency count of `arr[index]`. If the frequency goes from 1 to 0, decrement the distinct count.\n\nBoth operations are O(1), which is critical. Mo's Algorithm only works efficiently when add and remove are fast.\n\n\n```mermaid\nflowchart TD\n A[\"For each query
in sorted order\"]:::primary --> B{\"curR < R?\"}:::orange\n B -->|Yes| C[\"curR++
add(curR)\"]:::green\n C --> B\n B -->|No| D{\"curR > R?\"}:::orange\n D -->|Yes| E[\"remove(curR)
curR--\"]:::red\n E --> D\n D -->|No| F{\"curL > L?\"}:::orange\n F -->|Yes| G[\"curL--
add(curL)\"]:::green\n G --> F\n F -->|No| H{\"curL < L?\"}:::orange\n H -->|Yes| I[\"remove(curL)
curL++\"]:::red\n I --> H\n H -->|No| J[\"answer[query.idx]
= currentAnswer\"]:::teal\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through a concrete example. Consider the array:\n\n\n```shell\narr = [1, 2, 1, 3, 2, 1, 4, 3] (0-indexed, n = 8)\n```\n\n\nBlock size `B = floor(sqrt(8)) = 2`.\n\nWe have 5 queries asking for the count of distinct elements in each range:\n\n\n| Query | L | R | Block of L |\n|-------|---|---|------------|\n| Q0 | 0 | 3 | 0 |\n| Q1 | 1 | 5 | 0 |\n| Q2 | 4 | 7 | 2 |\n| Q3 | 2 | 5 | 1 |\n| Q4 | 3 | 7 | 1 |\n\n\n### Sorting the Queries\n\nBlock assignments: Q0 is in block 0, Q1 is in block 0, Q3 is in block 1, Q4 is in block 1, Q2 is in block 2.\n\nWithin block 0 (even), sort by R ascending: Q0(R=3), then Q1(R=5). Within block 1 (odd), sort by R descending: Q4(R=7), then Q3(R=5). Block 2 has only Q2.\n\n**Sorted order:** Q0, Q1, Q4, Q3, Q2.\n\n### Processing Query by Query\n\nWe start with curL = 0, curR = -1, distinctCount = 0, and an empty frequency array.\n\n**Processing Q0: [0, 3]**\n\n\n```shell\nExpand right: curR = -1 -> 3\n add(0): arr[0]=1, freq[1]: 0->1, distinctCount: 0->1\n add(1): arr[1]=2, freq[2]: 0->1, distinctCount: 1->2\n add(2): arr[2]=1, freq[1]: 1->2, distinctCount stays 2\n add(3): arr[3]=3, freq[3]: 0->1, distinctCount: 2->3\n\nWindow: [0, 3], distinctCount = 3\nAnswer for Q0 = 3 (elements: 1,2,1,3 -> 3 distinct)\n```\n\n\n**Processing Q1: [1, 5]**\n\n\n```shell\nExpand right: curR = 3 -> 5\n add(4): arr[4]=2, freq[2]: 1->2, distinctCount stays 3\n add(5): arr[5]=1, freq[1]: 2->3, distinctCount stays 3\n\nShrink left: curL = 0 -> 1\n remove(0): arr[0]=1, freq[1]: 3->2, distinctCount stays 3\n\nWindow: [1, 5], distinctCount = 3\nAnswer for Q1 = 3 (elements: 2,1,3,2,1 -> 3 distinct)\n```\n\n\n**Processing Q4: [3, 7]**\n\n\n```shell\nExpand right: curR = 5 -> 7\n add(6): arr[6]=4, freq[4]: 0->1, distinctCount: 3->4\n add(7): arr[7]=3, freq[3]: 1->2, distinctCount stays 4\n\nShrink left: curL = 1 -> 3\n remove(1): arr[1]=2, freq[2]: 2->1, distinctCount stays 4\n remove(2): arr[2]=1, freq[1]: 2->1, distinctCount stays 4\n\nWindow: [3, 7], distinctCount = 4\nAnswer for Q4 = 4 (elements: 3,2,1,4,3 -> 4 distinct)\n```\n\n\n**Processing Q3: [2, 5]**\n\n\n```shell\nShrink right: curR = 7 -> 5\n remove(7): arr[7]=3, freq[3]: 2->1, distinctCount stays 4\n remove(6): arr[6]=4, freq[4]: 1->0, distinctCount: 4->3\n\nExpand left: curL = 3 -> 2\n add(2): arr[2]=1, freq[1]: 1->2, distinctCount stays 3\n\nWindow: [2, 5], distinctCount = 3\nAnswer for Q3 = 3 (elements: 1,3,2,1 -> 3 distinct)\n```\n\n\n**Processing Q2: [4, 7]**\n\n\n```shell\nExpand right: curR = 5 -> 7\n add(6): arr[6]=4, freq[4]: 0->1, distinctCount: 3->4\n add(7): arr[7]=3, freq[3]: 1->2, distinctCount stays 4\n\nShrink left: curL = 2 -> 4\n remove(2): arr[2]=1, freq[1]: 2->1, distinctCount stays 4\n remove(3): arr[3]=3, freq[3]: 2->1, distinctCount stays 4\n\nWindow: [4, 7], distinctCount = 4\nAnswer for Q2 = 4 (elements: 2,1,4,3 -> 4 distinct)\n```\n\n\n### Final Answers\n\n\n| Query | Range | Distinct Count |\n|-------|-------|----------------|\n| Q0 | [0, 3] | 3 |\n| Q1 | [1, 5] | 3 |\n| Q2 | [4, 7] | 4 |\n| Q3 | [2, 5] | 3 |\n| Q4 | [3, 7] | 4 |\n\n\nNotice how the pointers moved relatively small distances between consecutive queries in sorted order. That is the whole point.\n\n---\n\n# Implementation\n\nHere is a complete implementation of Mo's Algorithm for counting distinct elements in a range. The queries are sorted by the block of their left endpoint with an alternating sort direction on the right endpoint, then answered with a two-pointer window that adds and removes elements while maintaining a running count of distinct values.\n\n\n```java\nimport java.util.*;\n\npublic class MosAlgorithm {\n\n static int blockSize;\n static int[] freq;\n static int distinctCount;\n\n public static int[] solve(int[] arr, int[][] queries) {\n int n = arr.length;\n int q = queries.length;\n blockSize = Math.max(1, (int) Math.sqrt(n));\n\n // Build query objects: {L, R, original index}\n int[][] sortedQueries = new int[q][3];\n for (int i = 0; i < q; i++) {\n sortedQueries[i][0] = queries[i][0]; // L\n sortedQueries[i][1] = queries[i][1]; // R\n sortedQueries[i][2] = i; // original index\n }\n\n // Sort queries by (block of L, then R with alternating direction)\n Arrays.sort(sortedQueries, (a, b) -> {\n int blockA = a[0] / blockSize;\n int blockB = b[0] / blockSize;\n if (blockA != blockB) return blockA - blockB;\n // Alternating sort: even blocks ascending R, odd blocks descending R\n return (blockA % 2 == 0) ? a[1] - b[1] : b[1] - a[1];\n });\n\n // Find max value for frequency array\n int maxVal = 0;\n for (int val : arr) maxVal = Math.max(maxVal, val);\n freq = new int[maxVal + 1];\n distinctCount = 0;\n\n int[] answers = new int[q];\n int curL = 0, curR = -1;\n\n for (int[] query : sortedQueries) {\n int L = query[0], R = query[1], idx = query[2];\n\n // Expand right\n while (curR < R) add(arr, ++curR);\n // Shrink right\n while (curR > R) remove(arr, curR--);\n // Expand left\n while (curL > L) add(arr, --curL);\n // Shrink left\n while (curL < L) remove(arr, curL++);\n\n answers[idx] = distinctCount;\n }\n return answers;\n }\n\n static void add(int[] arr, int index) {\n freq[arr[index]]++;\n if (freq[arr[index]] == 1) distinctCount++;\n }\n\n static void remove(int[] arr, int index) {\n freq[arr[index]]--;\n if (freq[arr[index]] == 0) distinctCount--;\n }\n\n public static void main(String[] args) {\n int[] arr = {1, 2, 1, 3, 2, 1, 4, 3};\n int[][] queries = {{0, 3}, {1, 5}, {4, 7}, {2, 5}, {3, 7}};\n int[] results = solve(arr, queries);\n for (int i = 0; i < results.length; i++) {\n System.out.println(\"Query \" + i + \": \" + results[i]);\n }\n }\n}\n```\n\n```python\nimport math\n\ndef mos_algorithm(arr, queries):\n \"\"\"\n Mo's Algorithm for counting distinct elements in range [L, R].\n\n Time Complexity: O((n + q) * sqrt(n))\n Space Complexity: O(n + max_val)\n \"\"\"\n n = len(arr)\n q = len(queries)\n block_size = max(1, int(math.sqrt(n)))\n\n # Attach original index to each query\n indexed_queries = [(L, R, i) for i, (L, R) in enumerate(queries)]\n\n # Sort by (block of L, then R with alternating direction)\n def sort_key(query):\n L, R, _ = query\n block = L // block_size\n # Alternating: even blocks sort R ascending, odd blocks descending\n return (block, R if block % 2 == 0 else -R)\n\n indexed_queries.sort(key=sort_key)\n\n # Frequency array and state\n max_val = max(arr)\n freq = [0] * (max_val + 1)\n distinct_count = 0\n answers = [0] * q\n\n cur_l, cur_r = 0, -1\n\n def add(index):\n nonlocal distinct_count\n freq[arr[index]] += 1\n if freq[arr[index]] == 1:\n distinct_count += 1\n\n def remove(index):\n nonlocal distinct_count\n freq[arr[index]] -= 1\n if freq[arr[index]] == 0:\n distinct_count -= 1\n\n for L, R, idx in indexed_queries:\n # Expand right\n while cur_r < R:\n cur_r += 1\n add(cur_r)\n # Shrink right\n while cur_r > R:\n remove(cur_r)\n cur_r -= 1\n # Expand left\n while cur_l > L:\n cur_l -= 1\n add(cur_l)\n # Shrink left\n while cur_l < L:\n remove(cur_l)\n cur_l += 1\n\n answers[idx] = distinct_count\n\n return answers\n\n# Example usage\narr = [1, 2, 1, 3, 2, 1, 4, 3]\nqueries = [(0, 3), (1, 5), (4, 7), (2, 5), (3, 7)]\nresults = mos_algorithm(arr, queries)\nfor i, result in enumerate(results):\n print(f\"Query {i}: {result}\")\n```\n\n```cpp\n#include \nusing namespace std;\n\nint blockSize;\nint freq[1000001];\nint distinctCount = 0;\n\nstruct Query {\n int L, R, idx;\n};\n\nvoid add(int* arr, int index) {\n freq[arr[index]]++;\n if (freq[arr[index]] == 1) distinctCount++;\n}\n\nvoid removeEl(int* arr, int index) {\n freq[arr[index]]--;\n if (freq[arr[index]] == 0) distinctCount--;\n}\n\nbool compare(const Query& a, const Query& b) {\n int blockA = a.L / blockSize;\n int blockB = b.L / blockSize;\n if (blockA != blockB) return blockA < blockB;\n // Alternating sort direction for R\n return (blockA % 2 == 0) ? (a.R < b.R) : (a.R > b.R);\n}\n\nvector mosAlgorithm(int arr[], int n, vector& queries) {\n int q = queries.size();\n blockSize = max(1, (int)sqrt(n));\n\n sort(queries.begin(), queries.end(), compare);\n\n vector answers(q);\n int curL = 0, curR = -1;\n\n for (auto& query : queries) {\n int L = query.L, R = query.R;\n\n // Expand right\n while (curR < R) add(arr, ++curR);\n // Shrink right\n while (curR > R) removeEl(arr, curR--);\n // Expand left\n while (curL > L) add(arr, --curL);\n // Shrink left\n while (curL < L) removeEl(arr, curL++);\n\n answers[query.idx] = distinctCount;\n }\n return answers;\n}\n\nint main() {\n int arr[] = {1, 2, 1, 3, 2, 1, 4, 3};\n int n = 8;\n vector queries = {{0, 3, 0}, {1, 5, 1}, {4, 7, 2}, {2, 5, 3}, {3, 7, 4}};\n\n vector results = mosAlgorithm(arr, n, queries);\n for (int i = 0; i < (int)results.size(); i++) {\n cout << \"Query \" << i << \": \" << results[i] << endl;\n }\n return 0;\n}\n```\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class MosAlgorithm {\n\n static int blockSize;\n static int[] freq;\n static int distinctCount;\n\n public static int[] Solve(int[] arr, int[][] queries) {\n int n = arr.Length;\n int q = queries.Length;\n blockSize = Math.Max(1, (int)Math.Sqrt(n));\n\n // Build query objects: {L, R, original index}\n int[][] sortedQueries = new int[q][];\n for (int i = 0; i < q; i++) {\n sortedQueries[i] = new int[] { queries[i][0], queries[i][1], i };\n }\n\n // Sort queries by (block of L, then R with alternating direction)\n Array.Sort(sortedQueries, (a, b) => {\n int blockA = a[0] / blockSize;\n int blockB = b[0] / blockSize;\n if (blockA != blockB) return blockA - blockB;\n // Alternating sort: even blocks ascending R, odd blocks descending R\n return (blockA % 2 == 0) ? a[1] - b[1] : b[1] - a[1];\n });\n\n // Find max value for frequency array\n int maxVal = 0;\n foreach (int val in arr) maxVal = Math.Max(maxVal, val);\n freq = new int[maxVal + 1];\n distinctCount = 0;\n\n int[] answers = new int[q];\n int curL = 0, curR = -1;\n\n foreach (int[] query in sortedQueries) {\n int L = query[0], R = query[1], idx = query[2];\n\n // Expand right\n while (curR < R) Add(arr, ++curR);\n // Shrink right\n while (curR > R) Remove(arr, curR--);\n // Expand left\n while (curL > L) Add(arr, --curL);\n // Shrink left\n while (curL < L) Remove(arr, curL++);\n\n answers[idx] = distinctCount;\n }\n return answers;\n }\n\n static void Add(int[] arr, int index) {\n freq[arr[index]]++;\n if (freq[arr[index]] == 1) distinctCount++;\n }\n\n static void Remove(int[] arr, int index) {\n freq[arr[index]]--;\n if (freq[arr[index]] == 0) distinctCount--;\n }\n\n public static void Main(string[] args) {\n int[] arr = { 1, 2, 1, 3, 2, 1, 4, 3 };\n int[][] queries = {\n new int[] { 0, 3 }, new int[] { 1, 5 }, new int[] { 4, 7 },\n new int[] { 2, 5 }, new int[] { 3, 7 }\n };\n int[] results = Solve(arr, queries);\n for (int i = 0; i < results.Length; i++) {\n Console.WriteLine(\"Query \" + i + \": \" + results[i]);\n }\n }\n}\n```\n\n```go\npackage main\n\nimport (\n\t\"fmt\"\n\t\"math\"\n\t\"sort\"\n)\n\nvar (\n\tblockSize int\n\tfreq []int\n\tdistinctCount int\n)\n\nfunc add(arr []int, index int) {\n\tfreq[arr[index]]++\n\tif freq[arr[index]] == 1 {\n\t\tdistinctCount++\n\t}\n}\n\nfunc remove(arr []int, index int) {\n\tfreq[arr[index]]--\n\tif freq[arr[index]] == 0 {\n\t\tdistinctCount--\n\t}\n}\n\nfunc mosAlgorithm(arr []int, queries [][2]int) []int {\n\tn := len(arr)\n\tq := len(queries)\n\tblockSize = int(math.Sqrt(float64(n)))\n\tif blockSize < 1 {\n\t\tblockSize = 1\n\t}\n\n\t// Build query objects: {L, R, original index}\n\tsortedQueries := make([][3]int, q)\n\tfor i := 0; i < q; i++ {\n\t\tsortedQueries[i] = [3]int{queries[i][0], queries[i][1], i}\n\t}\n\n\t// Sort queries by (block of L, then R with alternating direction)\n\tsort.Slice(sortedQueries, func(i, j int) bool {\n\t\ta, b := sortedQueries[i], sortedQueries[j]\n\t\tblockA := a[0] / blockSize\n\t\tblockB := b[0] / blockSize\n\t\tif blockA != blockB {\n\t\t\treturn blockA < blockB\n\t\t}\n\t\t// Alternating sort: even blocks ascending R, odd blocks descending R\n\t\tif blockA%2 == 0 {\n\t\t\treturn a[1] < b[1]\n\t\t}\n\t\treturn a[1] > b[1]\n\t})\n\n\t// Find max value for frequency array\n\tmaxVal := 0\n\tfor _, val := range arr {\n\t\tif val > maxVal {\n\t\t\tmaxVal = val\n\t\t}\n\t}\n\tfreq = make([]int, maxVal+1)\n\tdistinctCount = 0\n\n\tanswers := make([]int, q)\n\tcurL, curR := 0, -1\n\n\tfor _, query := range sortedQueries {\n\t\tL, R, idx := query[0], query[1], query[2]\n\n\t\t// Expand right\n\t\tfor curR < R {\n\t\t\tcurR++\n\t\t\tadd(arr, curR)\n\t\t}\n\t\t// Shrink right\n\t\tfor curR > R {\n\t\t\tremove(arr, curR)\n\t\t\tcurR--\n\t\t}\n\t\t// Expand left\n\t\tfor curL > L {\n\t\t\tcurL--\n\t\t\tadd(arr, curL)\n\t\t}\n\t\t// Shrink left\n\t\tfor curL < L {\n\t\t\tremove(arr, curL)\n\t\t\tcurL++\n\t\t}\n\n\t\tanswers[idx] = distinctCount\n\t}\n\treturn answers\n}\n\nfunc main() {\n\tarr := []int{1, 2, 1, 3, 2, 1, 4, 3}\n\tqueries := [][2]int{{0, 3}, {1, 5}, {4, 7}, {2, 5}, {3, 7}}\n\tresults := mosAlgorithm(arr, queries)\n\tfor i, result := range results {\n\t\tfmt.Printf(\"Query %d: %d\\n\", i, result)\n\t}\n}\n```\n\n```rust\nfn add(arr: &[usize], index: usize, freq: &mut [i32], distinct_count: &mut i32) {\n freq[arr[index]] += 1;\n if freq[arr[index]] == 1 {\n *distinct_count += 1;\n }\n}\n\nfn remove(arr: &[usize], index: usize, freq: &mut [i32], distinct_count: &mut i32) {\n freq[arr[index]] -= 1;\n if freq[arr[index]] == 0 {\n *distinct_count -= 1;\n }\n}\n\nfn mos_algorithm(arr: &[usize], queries: &[(usize, usize)]) -> Vec {\n let n = arr.len();\n let q = queries.len();\n let block_size = ((n as f64).sqrt() as usize).max(1);\n\n // Build query objects: (L, R, original index)\n let mut sorted_queries: Vec<(usize, usize, usize)> = queries\n .iter()\n .enumerate()\n .map(|(i, &(l, r))| (l, r, i))\n .collect();\n\n // Sort queries by (block of L, then R with alternating direction)\n sorted_queries.sort_by(|a, b| {\n let block_a = a.0 / block_size;\n let block_b = b.0 / block_size;\n if block_a != block_b {\n return block_a.cmp(&block_b);\n }\n // Alternating sort: even blocks ascending R, odd blocks descending R\n if block_a % 2 == 0 {\n a.1.cmp(&b.1)\n } else {\n b.1.cmp(&a.1)\n }\n });\n\n // Find max value for frequency array\n let max_val = *arr.iter().max().unwrap_or(&0);\n let mut freq = vec![0i32; max_val + 1];\n let mut distinct_count = 0;\n\n let mut answers = vec![0; q];\n let mut cur_l: usize = 0;\n let mut cur_r: i64 = -1;\n\n for &(l, r, idx) in &sorted_queries {\n let r = r as i64;\n let l = l as i64;\n\n // Expand right\n while cur_r < r {\n cur_r += 1;\n add(arr, cur_r as usize, &mut freq, &mut distinct_count);\n }\n // Shrink right\n while cur_r > r {\n remove(arr, cur_r as usize, &mut freq, &mut distinct_count);\n cur_r -= 1;\n }\n // Expand left\n while (cur_l as i64) > l {\n cur_l -= 1;\n add(arr, cur_l, &mut freq, &mut distinct_count);\n }\n // Shrink left\n while (cur_l as i64) < l {\n remove(arr, cur_l, &mut freq, &mut distinct_count);\n cur_l += 1;\n }\n\n answers[idx] = distinct_count;\n }\n answers\n}\n\nfn main() {\n let arr = vec![1, 2, 1, 3, 2, 1, 4, 3];\n let queries = vec![(0, 3), (1, 5), (4, 7), (2, 5), (3, 7)];\n let results = mos_algorithm(&arr, &queries);\n for (i, result) in results.iter().enumerate() {\n println!(\"Query {}: {}\", i, result);\n }\n}\n```\n\n```javascript\nfunction mosAlgorithm(arr, queries) {\n const n = arr.length;\n const q = queries.length;\n const blockSize = Math.max(1, Math.floor(Math.sqrt(n)));\n\n // Build query objects: [L, R, original index]\n const sortedQueries = queries.map(([L, R], i) => [L, R, i]);\n\n // Sort queries by (block of L, then R with alternating direction)\n sortedQueries.sort((a, b) => {\n const blockA = Math.floor(a[0] / blockSize);\n const blockB = Math.floor(b[0] / blockSize);\n if (blockA !== blockB) return blockA - blockB;\n // Alternating sort: even blocks ascending R, odd blocks descending R\n return blockA % 2 === 0 ? a[1] - b[1] : b[1] - a[1];\n });\n\n // Find max value for frequency array\n let maxVal = 0;\n for (const val of arr) maxVal = Math.max(maxVal, val);\n const freq = new Array(maxVal + 1).fill(0);\n let distinctCount = 0;\n\n const answers = new Array(q).fill(0);\n let curL = 0;\n let curR = -1;\n\n const add = (index) => {\n freq[arr[index]]++;\n if (freq[arr[index]] === 1) distinctCount++;\n };\n\n const remove = (index) => {\n freq[arr[index]]--;\n if (freq[arr[index]] === 0) distinctCount--;\n };\n\n for (const [L, R, idx] of sortedQueries) {\n // Expand right\n while (curR < R) add(++curR);\n // Shrink right\n while (curR > R) remove(curR--);\n // Expand left\n while (curL > L) add(--curL);\n // Shrink left\n while (curL < L) remove(curL++);\n\n answers[idx] = distinctCount;\n }\n return answers;\n}\n\n// Example usage\nconst arr = [1, 2, 1, 3, 2, 1, 4, 3];\nconst queries = [[0, 3], [1, 5], [4, 7], [2, 5], [3, 7]];\nconst results = mosAlgorithm(arr, queries);\nresults.forEach((result, i) => {\n console.log(`Query ${i}: ${result}`);\n});\n```\n\n```typescript\nfunction mosAlgorithm(arr: number[], queries: [number, number][]): number[] {\n const n = arr.length;\n const q = queries.length;\n const blockSize = Math.max(1, Math.floor(Math.sqrt(n)));\n\n // Build query objects: [L, R, original index]\n const sortedQueries: [number, number, number][] = queries.map(\n ([L, R], i) => [L, R, i]\n );\n\n // Sort queries by (block of L, then R with alternating direction)\n sortedQueries.sort((a, b) => {\n const blockA = Math.floor(a[0] / blockSize);\n const blockB = Math.floor(b[0] / blockSize);\n if (blockA !== blockB) return blockA - blockB;\n // Alternating sort: even blocks ascending R, odd blocks descending R\n return blockA % 2 === 0 ? a[1] - b[1] : b[1] - a[1];\n });\n\n // Find max value for frequency array\n let maxVal = 0;\n for (const val of arr) maxVal = Math.max(maxVal, val);\n const freq: number[] = new Array(maxVal + 1).fill(0);\n let distinctCount = 0;\n\n const answers: number[] = new Array(q).fill(0);\n let curL = 0;\n let curR = -1;\n\n const add = (index: number): void => {\n freq[arr[index]]++;\n if (freq[arr[index]] === 1) distinctCount++;\n };\n\n const remove = (index: number): void => {\n freq[arr[index]]--;\n if (freq[arr[index]] === 0) distinctCount--;\n };\n\n for (const [L, R, idx] of sortedQueries) {\n // Expand right\n while (curR < R) add(++curR);\n // Shrink right\n while (curR > R) remove(curR--);\n // Expand left\n while (curL > L) add(--curL);\n // Shrink left\n while (curL < L) remove(curL++);\n\n answers[idx] = distinctCount;\n }\n return answers;\n}\n\n// Example usage\nconst arr: number[] = [1, 2, 1, 3, 2, 1, 4, 3];\nconst queries: [number, number][] = [[0, 3], [1, 5], [4, 7], [2, 5], [3, 7]];\nconst results = mosAlgorithm(arr, queries);\nresults.forEach((result, i) => {\n console.log(`Query ${i}: ${result}`);\n});\n```\n\n\n---\n\n# Code Explanation\n\nLet us walk through the key parts of the implementation.\n\n**Query sorting.** The comparator is the heart of the algorithm. It first groups queries by the block their left endpoint falls in (`L / blockSize`). Within the same block, it sorts by R, with even-numbered blocks sorting R ascending and odd-numbered blocks sorting R descending. This alternating pattern prevents the right pointer from jumping back to the start when transitioning between blocks.\n\n**The main loop.** For each query in sorted order, four while-loops adjust the current window `[curL, curR]` to match the query's `[L, R]`. The order of these loops (expand right, shrink right, expand left, shrink left) ensures the window is always valid. After adjustment, the current answer is stored at the query's original index.\n\n**add and remove functions.** These maintain a frequency array and a running distinct count. When adding an element, if its frequency increases from 0 to 1, it is a new distinct element. When removing, if its frequency drops from 1 to 0, we lose a distinct element. Both are O(1).\n\n**Common Mistakes:**\n\n- **Forgetting the original index.** If you do not store each query's original position and write the answer back to it, your answers will be in the sorted order instead of the input order. This is the single most common bug.\n- **Off-by-one in the block size.** Using `blockSize = 0` when `n = 0` causes division by zero. Always use `max(1, sqrt(n))`.\n- **Wrong expand/shrink order.** Expanding before shrinking keeps the window valid. If you shrink left before expanding right, you might temporarily have `curL > curR`, and your add/remove functions could behave unexpectedly.\n- **Skipping the tie-breaking optimization.** Without the alternating R sort direction, the algorithm still works correctly, but the right pointer wastes O(n) movement at every block boundary. On tight time limits, this matters.\n\n---\n\n# Complexity Analysis\n\n### Time Complexity\n\n**Overall:** O((n + q) * sqrt(n))\n\nThis is the key claim. Let us break it down carefully.\n\n**Right pointer analysis.** Within a single block of left endpoints, all queries have their L values in the same block of size sqrt(n). Since queries within a block are sorted by R (ascending or descending), the right pointer moves monotonically within each block. In the worst case, R sweeps across all n elements, so the right pointer moves at most O(n) per block. There are sqrt(n) blocks, giving O(n * sqrt(n)) total movement for the right pointer.\n\n**Left pointer analysis.** When moving from one query to the next within the same block, the left endpoints differ by at most sqrt(n) (since they are all in the same block). So the left pointer moves at most O(sqrt(n)) per query. Across all q queries, that is O(q * sqrt(n)).\n\n**Combined:** O(n * sqrt(n)) for the right pointer + O(q * sqrt(n)) for the left pointer = **O((n + q) * sqrt(n))**.\n\nFor the typical case where n and q are roughly equal (both around 10^5), this gives approximately 10^5 * 316 = 3.16 * 10^7, which is very comfortable within a 1-2 second time limit.\n\n\n| Component | Movement per Block | Blocks | Total |\n|-----------|-------------------|--------|-------|\n| Right pointer | O(n) | sqrt(n) | O(n * sqrt(n)) |\n| Left pointer | O(sqrt(n)) per query | q queries | O(q * sqrt(n)) |\n| **Total** | | | **O((n + q) * sqrt(n))** |\n\n\n### Space Complexity\n\n**Overall:** O(n + q + max_val)\n\n- **Frequency array:** O(max_val) or O(n) if you coordinate-compress the values.\n- **Query storage:** O(q) for storing the sorted queries with their original indices.\n- **Answer array:** O(q).\n\nIn practice, if array values can be large, you should coordinate-compress them to the range [0, n) before running Mo's Algorithm. This keeps the frequency array at O(n).\n\n---\n\n# Variations and Extensions\n\n### Mo's Algorithm with Updates (Mo's with Modifications)\n\nStandard Mo's is an offline algorithm for static arrays. But what if the array is modified between queries? Mo's with modifications (sometimes called \"Mo's Algorithm with time\") handles this.\n\nThe idea is to add a third dimension: time. Each query becomes (L, R, T), where T is the number of updates applied before this query. You sort queries by (block of L, block of R, T), using a block size of approximately n^(2/3) instead of sqrt(n).\n\nWhen processing queries, you move three pointers: left, right, and time. Moving the time pointer forward applies an update, and moving it backward undoes the update. The total complexity becomes **O(n^(5/3))** for n queries and n updates.\n\n### Mo's Algorithm on Trees\n\nMo's Algorithm is designed for arrays, but many tree problems can be reduced to array problems using an Euler tour. The Euler tour flattens the tree into an array, and paths or subtrees become ranges in that array. Once flattened, you apply standard Mo's on the resulting array.\n\nThe main subtlety is handling LCA queries. For a path from node u to node v, the Euler tour range might not directly correspond to the path. You need to handle the LCA node specially, sometimes adding it separately.\n\n### Block Size Optimization\n\nThe standard block size is sqrt(n), but the optimal block size depends on the ratio of n to q. If you have many more queries than array elements, a smaller block size helps. The theoretically optimal block size is:\n\n\n```shell\nB = max(1, n / sqrt(q)) when n and q differ significantly\n```\n\n\nFor the common case where n is roughly equal to q, this simplifies back to sqrt(n).\n\n### Comparison Table\n\n\n| Variant | Time Complexity | Block Size | Handles Updates? | Works on Trees? |\n|---------|----------------|------------|------------------|-----------------|\n| Standard Mo's | O((n+q) * sqrt(n)) | sqrt(n) | No | No |\n| Mo's with Updates | O(n^(5/3)) | n^(2/3) | Yes | No |\n| Mo's on Trees | O((n+q) * sqrt(n)) | sqrt(n) | No | Yes |\n| Mo's with Updates + Trees | O(n^(5/3)) | n^(2/3) | Yes | Yes |\n\n\n---\n\n# Comparison with Related Structures\n\nWhen should you choose Mo's Algorithm over other approaches? Here is how it stacks up.\n\n\n| Approach | Time per Query | Build Time | Handles Updates? | Query Types |\n|----------|---------------|------------|------------------|-------------|\n| Mo's Algorithm | O(sqrt(n)) amortized | O(q * sqrt(n)) total | No (standard) | Any decomposable aggregate |\n| Segment Tree | O(log n) | O(n) | Yes | Associative, mergeable aggregates |\n| Sqrt Decomposition | O(sqrt(n)) | O(n) | Yes | Specific to decomposition design |\n| Persistent Segment Tree | O(log n) | O(n log n) | Via versioning | Associative, mergeable aggregates |\n| Merge Sort Tree | O(log^2 n) | O(n log n) | No | Order statistics, count less than k |\n\n\n### When to Choose Mo's Algorithm\n\n- **The aggregate is hard to merge.** Counting distinct elements, computing the mode, or tracking frequency distributions are difficult to handle with segment trees because there is no efficient merge operation. Mo's sidesteps this entirely.\n- **All queries are known upfront.** Mo's is offline. If queries arrive one at a time and need immediate answers, you cannot use it.\n- **The add/remove operations are O(1).** Mo's works best when updating the window by one element is fast. If add/remove is O(log n), the total complexity becomes O((n + q) * sqrt(n) * log n), which may be too slow.\n\n### When NOT to Use Mo's Algorithm\n\n- **Online queries.** If you must answer each query before seeing the next one, Mo's is not an option. Use a segment tree or persistent structure instead.\n- **Tight time limits with n > 2 * 10^5.** Mo's has a large constant factor compared to segment trees. For very large inputs, O(n * sqrt(n)) might be too slow even though it is sub-quadratic.\n- **The problem has efficient merge.** If the aggregate is something like \"range sum\" or \"range min,\" a segment tree answers each query in O(log n), which is strictly faster than Mo's O(sqrt(n)) amortized.\n\n---\n\n# Common Patterns and Applications\n\n### Pattern 1: Distinct Elements in a Range\n\n**Problem type:** Given an array and multiple queries [L, R], count the number of distinct elements in each range.\n\n**How Mo's helps:** Maintain a frequency array. When adding an element, if its frequency goes from 0 to 1, increment the distinct count. When removing, if it drops to 0, decrement. This is the classic Mo's application.\n\n### Pattern 2: Sum of Squares of Frequencies\n\n**Problem type:** For each query [L, R], compute the sum of f(x)^2 for all values x, where f(x) is the frequency of x in the range.\n\n**How Mo's helps:** Maintain a running sum. When adding element x with current frequency f, subtract f^2, increment f, and add (f+1)^2. The net change is +2f+1. Similarly for removal. Both are O(1).\n\n### Pattern 3: XOR of Distinct Elements\n\n**Problem type:** For each query [L, R], compute the XOR of all distinct elements in the range.\n\n**How Mo's helps:** Maintain a frequency array and a running XOR. When an element's frequency goes from 0 to 1, XOR it into the result. When it drops from 1 to 0, XOR it out (XOR is its own inverse). O(1) add and remove.\n\n### Pattern 4: Powerful Array (Codeforces 86D)\n\n**Problem type:** For each query, compute the sum of count(x)^2 * x over all values x in the range.\n\n**How Mo's helps:** When adding element x with current count c, the contribution changes from c^2 * x to (c+1)^2 * x. The delta is (2c + 1) * x. When removing, the delta is -(2c - 1) * x. Both are O(1) updates to a running sum.\n\n### Interview Tips\n\n1. **Identify offline range queries early.** If the problem gives you all queries upfront and the aggregate is unusual (distinct count, mode, etc.), think Mo's.\n2. **Design add/remove first.** Before writing any Mo's framework code, figure out how to update your answer when adding or removing a single element. If this takes O(1), Mo's will work.\n3. **Coordinate compress if needed.** If array values can be up to 10^9, map them down to [0, n) so your frequency array fits in memory.\n4. **Watch the block size.** Use `max(1, (int)sqrt(n))` to avoid division by zero and get a good balance between left and right pointer movement.\n5. **Always verify with the example.** Mo's bugs are subtle. Trace through 2-3 queries by hand after coding to catch off-by-one and ordering issues.\n\n---\n\n# Summary\n\n### Key Takeaways\n\n- Mo's Algorithm is an offline technique for answering range queries in O((n + q) * sqrt(n)) time, by sorting queries to minimize pointer movement.\n- The algorithm divides the array into blocks of size sqrt(n) and sorts queries by (block of L, R). Processing them in this order ensures the left pointer moves at most sqrt(n) per query and the right pointer sweeps at most n per block.\n- The critical requirement is that the `add` and `remove` functions must be O(1). If you can maintain your aggregate by adding or removing one element at a time, Mo's will work.\n- The alternating R sort direction (ascending for even blocks, descending for odd blocks) is a practical optimization that can nearly halve runtime by smoothing right-pointer transitions at block boundaries.\n- Mo's is the go-to approach when the aggregate is hard to merge (distinct count, mode, frequency statistics), making segment trees impractical.\n\n### Quick Reference\n\n\n| Aspect | Details |\n|--------|---------|\n| **Time Complexity** | O((n + q) * sqrt(n)) |\n| **Space Complexity** | O(n + q + max_val) |\n| **Prerequisites** | All queries known upfront (offline), add/remove in O(1) |\n| **Best For** | Non-mergeable aggregates: distinct count, frequency queries, mode |\n| **Avoid When** | Online queries, simple aggregates (use segment tree), very large n (>2*10^5 with tight TL) |\n| **Block Size** | sqrt(n), or n/sqrt(q) if n and q differ significantly |\n| **Key Optimization** | Alternate R sort direction in even/odd blocks |\n","pageType":"dsa"}

Mo's Algorithm

Ashish Pratap Singh

Get Premium