Mo’s Algorithm is a truly versatile algorithm that finds utility in a vast array of problems requiring querying an array or a list for a subarray. Now, let me tell you, this algorithm owes its efficiency to a very specific order of processing the queries, which significantly reduces the time required to access the array elements.
How does Mo’s Algorithm work?
- The algorithm starts by dividing the input array into blocks of a fixed size, and each block comprises sqrt(N) elements, where N denotes the size of the input array. Then, the algorithm sorts the requests according to the block index to which they belong.
- Now, the interesting part is that the queries are handled in sorted order, and a two-pointer technique facilitates the query’s transition from one block to another.
- No need to process every single element in each block, which speeds up the overall query time substantially.
- The time complexity of Mo’s Algorithm is O((N+Q)*sqrt(N)), where N is the size of the input array, and Q is the number of queries.
Mo’s Algorithm with Updates
Mo’s Algorithm with updates is an extension of the original algorithm that permits efficient updates to the input array while maintaining the same query time complexity. This is accomplished using a technique called Mo’s Algorithm with Lazy Propagation. Mo’s Algorithm with updates utilizes a lazy propagation technique to defer the update operation until a query necessitates it. The algorithm maintains a distinct array that monitors the pending updates, and the query time complexity remains identical to that of the original algorithm.
- Mo’s algorithm to efficiently respond to array range queries.
- It divides the array into sqrt(N) blocks, where N is the length of the array.
- The method then runs through each query, computing partial sums inside blocks and summing entire blocks.
Below is the Python implementation for Mo’s algorithm with updates:
C++
#include <bits/stdc++.h>using namespace std;// Nikunj Sonigara// Function to perform Mo's algorithm with updatesvector<int> mo_algorithm_with_update(vector<int>& array, vector<pair<int, int>>& queries, vector<pair<int, int>>& updates) { int block_size = sqrt(array.size()); vector<vector<int>> blocks(array.size() / block_size); // Dividing the input array into blocks for (int i = 0; i < array.size(); i++) { blocks[i / block_size].push_back(array[i]); } // Vector to store the answers for each query vector<int> answers; // Processing each query for (auto query : queries) { int start = query.first; int end = query.second; int start_block = start / block_size; int end_block = end / block_size; // If the query lies entirely within one block if (start_block == end_block) { int answer = accumulate(array.begin() + start, array.begin() + end + 1, 0); answers.push_back(answer); } else { // Summing values for the subarrays of different blocks int answer = accumulate(array.begin() + start, array.begin() + (start_block + 1) * block_size, 0); for (int i = start_block + 1; i < end_block; i++) { answer += accumulate(blocks[i].begin(), blocks[i].end(), 0); } answer += accumulate(array.begin() + end_block * block_size, array.begin() + end + 1, 0); answers.push_back(answer); } } // Applying updates to the array and blocks for (auto update : updates) { int index = update.first; int value = update.second; int block_index = index / block_size; array[index] = value; blocks[block_index] = vector<int>(array.begin() + block_index * block_size, array.begin() + (block_index + 1) * block_size); } return answers;}int main() { // Generating a random array of size 100 vector<int> array(100); random_device rd; mt19937 gen(rd()); uniform_int_distribution<> dis(0, 100); generate(array.begin(), array.end(), [&]() { return dis(gen); }); // Generating random queries vector<pair<int, int>> queries(10); generate(queries.begin(), queries.end(), [&]() { int start = dis(gen) % 100; int end = dis(gen) % 100; return make_pair(start, end); }); // Generating random updates vector<pair<int, int>> updates(5); generate(updates.begin(), updates.end(), [&]() { int index = dis(gen) % 100; int value = dis(gen) % 100; return make_pair(index, value); }); // Applying Mo's algorithm with updates vector<int> answers_with_update = mo_algorithm_with_update(array, queries, updates); // Printing the answers cout << "Answers with update:" << endl; for (int answer : answers_with_update) { cout << answer << endl; } return 0;} |
Java
import java.util.*;import java.util.stream.Collectors;class Pair<A, B> { private A first; private B second; public Pair(A first, B second) { this.first = first; this.second = second; } public A getFirst() { return first; } public B getSecond() { return second; }}public class MoAlgorithmWithUpdates { // Function to implement Mo's Algorithm with updates public static List<Integer> moAlgorithmWithUpdate(List<Integer> array, List<Pair<Integer, Integer>> queries, List<Pair<Integer, Integer>> updates) { // Determine the block size for dividing the array int block_size = (int) Math.sqrt(array.size()); List<List<Integer>> blocks = new ArrayList<>(); // Divide the input array into blocks for (int i = 0; i < array.size(); i += block_size) { // Create blocks of size 'block_size' or less for the last block blocks.add(array.subList(i, Math.min(i + block_size, array.size()))); } List<Integer> answers = new ArrayList<>(); // Process each query for (Pair<Integer, Integer> query : queries) { int start = query.getFirst(); int end = query.getSecond(); int start_block = start / block_size; int end_block = end / block_size; int answer = 0; if (start_block == end_block) { // Query falls within a single block, so calculate directly from the array for (int i = start; i <= end; i++) { answer += array.get(i); } } else { // Query spans multiple blocks for (int i = start; i < (start_block + 1) * block_size; i++) { answer += array.get(i); } for (int i = start_block + 1; i < end_block; i++) { // Sum the values in blocks between start_block and end_block answer += blocks.get(i).stream().mapToInt(Integer::intValue).sum(); } for (int i = end_block * block_size; i <= end; i++) { answer += array.get(i); } } answers.add(answer); } // Apply updates to the input array and corresponding blocks for (Pair<Integer, Integer> update : updates) { int index = update.getFirst(); int value = update.getSecond(); int block_index = index / block_size; // Update the value in the array array.set(index, value); // Update the corresponding block with the modified value blocks.set(block_index, new ArrayList<>(array.subList(block_index * block_size, Math.min((block_index + 1) * block_size, array.size())))); } return answers; } public static void main(String[] args) { // Generating a random array of size 100 List<Integer> array = new Random().ints(100, 0, 101).boxed().collect(Collectors.toList()); // Generating random queries List<Pair<Integer, Integer>> queries = new ArrayList<>(); Random rand = new Random(); for (int i = 0; i < 10; i++) { int start = rand.nextInt(100); int end = rand.nextInt(100); queries.add(new Pair<>(Math.min(start, end), Math.max(start, end))); } // Generating random updates List<Pair<Integer, Integer>> updates = new ArrayList<>(); for (int i = 0; i < 5; i++) { int index = rand.nextInt(100); int value = rand.nextInt(101); updates.add(new Pair<>(index, value)); } // Applying Mo's algorithm with updates List<Integer> answersWithUpdate = moAlgorithmWithUpdate(array, queries, updates); // Printing the answers System.out.println("Answers with update:"); for (int answer : answersWithUpdate) { System.out.println(answer); } }} |
Python3
import randomimport mathdef mo_algorithm_with_update(array, queries, updates): """ Answer range queries using Mo's algorithm with update. Args: array: The input array. queries: The range queries. updates: The update operations. Returns: The answers to the range queries after applying the updates. """ # Divide the input array into blocks of # size sqrt(N). block_size = int(math.sqrt(len(array))) blocks = [[] for _ in range(len(array) // block_size)] for i in range(len(array)): blocks[i // block_size].append(array[i]) # Create a data structure to store the # answers to the range queries. answers = [] # Answer the range queries. for query in queries: start, end = query start_block = start // block_size end_block = end // block_size if start_block == end_block: # If the query is contained within # a single block. answer = sum(array[start:end + 1]) else: # If the query spans multiple # blocks. # Partial sum in the start block answer = sum(array[start:(start_block + 1) * block_size]) # Sum of complete blocks answer += sum(sum(blocks[start_block + 1:end_block], [])) # Partial sum in the end block answer += sum(array[end_block * block_size:end + 1]) answers.append(answer) # Apply the update operations. for update in updates: index, value = update block_index = index // block_size array[index] = value blocks[block_index] = array[block_index * block_size:(block_index + 1) * block_size] return answers# Driver codedef main(): # Create an input array. array = [random.randint(0, 100) for _ in range(100)] # Create a list of range queries. queries = [] for _ in range(10): queries.append((random.randint(0, 99), random.randint(0, 99))) # Create a list of update operations. updates = [] for _ in range(5): updates.append((random.randint(0, 99), random.randint(0, 100))) # Answer the range queries using Mo's algorithm with update. answers_with_update = mo_algorithm_with_update(array, queries, updates) print("Answers with update:") for answer in answers_with_update: print(answer)if __name__ == "__main__": main() |
C#
using System;using System.Collections.Generic;using System.Linq;// Make Pair class publicpublic class Pair<A, B>{ private A first; private B second; public Pair(A first, B second) { this.first = first; this.second = second; } public A GetFirst() { return first; } public B GetSecond() { return second; }}public class MoAlgorithmWithUpdates{ // Function to implement Mo's Algorithm with updates public static List<int> MoAlgorithmWithUpdate(List<int> array, List<Pair<int, int>> queries, List<Pair<int, int>> updates) { // Determine the block size for dividing the array int blockSize = (int)Math.Sqrt(array.Count); List<List<int>> blocks = new List<List<int>>(); // Divide the input array into blocks for (int i = 0; i < array.Count; i += blockSize) { // Create blocks of size 'blockSize' or less for the last block blocks.Add(array.GetRange(i, Math.Min(blockSize, array.Count - i))); } List<int> answers = new List<int>(); // Process each query foreach (Pair<int, int> query in queries) { int start = query.GetFirst(); int end = query.GetSecond(); int startBlock = start / blockSize; int endBlock = end / blockSize; int answer = 0; if (startBlock == endBlock) { // Query falls within a single block, so calculate directly from the array for (int i = start; i <= end; i++) { answer += array[i]; } } else { // Query spans multiple blocks for (int i = start; i < (startBlock + 1) * blockSize; i++) { answer += array[i]; } for (int i = startBlock + 1; i < endBlock; i++) { // Sum the values in blocks between startBlock and endBlock answer += blocks[i].Sum(); } for (int i = endBlock * blockSize; i <= end; i++) { answer += array[i]; } } answers.Add(answer); } // Apply updates to the input array and corresponding blocks foreach (Pair<int, int> update in updates) { int index = update.GetFirst(); int value = update.GetSecond(); int blockIndex = index / blockSize; // Update the value in the array array[index] = value; // Update the corresponding block with the modified value int startRange = blockIndex * blockSize; int endRange = Math.Min((blockIndex + 1) * blockSize, array.Count); blocks[blockIndex] = new List<int>(array.GetRange(startRange, endRange - startRange)); } return answers; } public static void Main(string[] args) { // Generating a random array of size 100 List<int> array = Enumerable.Range(0, 100).Select(_ => new Random().Next(0, 101)).ToList(); // Generating random queries List<Pair<int, int>> queries = new List<Pair<int, int>>(); Random rand = new Random(); for (int i = 0; i < 10; i++) { int start = rand.Next(100); int end = rand.Next(100); queries.Add(new Pair<int, int>(Math.Min(start, end), Math.Max(start, end))); } // Generating random updates List<Pair<int, int>> updates = new List<Pair<int, int>>(); for (int i = 0; i < 5; i++) { int index = rand.Next(100); int value = rand.Next(101); updates.Add(new Pair<int, int>(index, value)); } // Applying Mo's algorithm with updates List<int> answersWithUpdate = MoAlgorithmWithUpdate(array, queries, updates); // Printing the answers Console.WriteLine("Answers with update:"); foreach (int answer in answersWithUpdate) { Console.WriteLine(answer); } }} |
Javascript
class Pair { constructor(first, second) { this.first = first; this.second = second; } getFirst() { return this.first; } getSecond() { return this.second; }}function moAlgorithmWithUpdate(array, queries, updates) { // Determine the block size for dividing the array const blockSize = Math.sqrt(array.length); const blocks = []; // Divide the input array into blocks for (let i = 0; i < array.length; i += blockSize) { // Create blocks of size 'blockSize' or less for the last block blocks.push(array.slice(i, Math.min(i + blockSize, array.length))); } const answers = []; // Process each query for (const query of queries) { const start = query.getFirst(); const end = query.getSecond(); const startBlock = Math.floor(start / blockSize); const endBlock = Math.floor(end / blockSize); let answer = 0; if (startBlock === endBlock) { // Query falls within a single block, so calculate directly from the array for (let i = start; i <= end; i++) { answer += array[i]; } } else { // Query spans multiple blocks for (let i = start; i < (startBlock + 1) * blockSize; i++) { answer += array[i]; } for (let i = startBlock + 1; i < endBlock; i++) { // Sum the values in blocks between startBlock and endBlock answer += blocks[i].reduce((acc, curr) => acc + curr, 0); } for (let i = endBlock * blockSize; i <= end; i++) { answer += array[i]; } } answers.push(answer); } // Apply updates to the input array and corresponding blocks for (const update of updates) { const index = update.getFirst(); const value = update.getSecond(); const blockIndex = Math.floor(index / blockSize); // Update the value in the array array[index] = value; // Update the corresponding block with the modified value blocks[blockIndex] = array.slice(blockIndex * blockSize, Math.min((blockIndex + 1) * blockSize, array.length)); } return answers;}// Generating a random array of size 100const array = Array.from({ length: 100 }, () => Math.floor(Math.random() * 101));// Generating random queriesconst queries = [];for (let i = 0; i < 10; i++) { const start = Math.floor(Math.random() * 100); const end = Math.floor(Math.random() * 100); queries.push(new Pair(Math.min(start, end), Math.max(start, end)));}// Generating random updatesconst updates = [];for (let i = 0; i < 5; i++) { const index = Math.floor(Math.random() * 100); const value = Math.floor(Math.random() * 101); updates.push(new Pair(index, value));}// Applying Mo's algorithm with updatesconst answersWithUpdate = moAlgorithmWithUpdate(array, queries, updates);// Printing the answersconsole.log("Answers with update:");for (const answer of answersWithUpdate) { console.log(answer);} |
Output
Answers with update: 598 117 341 794 788 480 4372 19 3146 1737
Time Complexity: O(Q * sqrt(N))
Auxiliary Space: O(sqrt(N))
Mo’s Algorithm without Updates
Mo’s Algorithm without Updates is the original algorithm which we discussed earlier in this the queries are handled in a sorted order, and a two-pointer technique facilitates the query’s transition from one block to another. No need to process every single element in each block, which speeds up the overall query time substantially.. This algorithm finds its utility in cases where the input array is static, and no updates are necessary.
- Mo’s Algorithm without updates is a solid choice when you’re dealing with static data and need to perform range queries like calculating the sum of elements in a subarray, locating the minimum or maximum element in a subarray, or determining the median of elements in a subarray.
- The provided code uses Mo’s algorithm without an update to efficiently respond to array range queries. It divides the array into sqrt(N) blocks, where N is the length of the array.
- The method then runs through each query, computing partial sums inside blocks and summing entire blocks.
Below is the Python implementation for Mo’s algorithm without updates:
C++
#include <iostream>#include <vector>#include <cmath>#include <algorithm>#include <cstdlib>#include <ctime>#include <numeric>std::vector<int> moAlgorithmWithoutUpdate(const std::vector<int>& array, const std::vector<std::pair<int, int>>& queries) { int n = array.size(); // Divide the input array into blocks of size sqrt(N). int blockSize = static_cast<int>(std::sqrt(n)); std::vector<std::vector<int>> blocks(n / blockSize + 1, std::vector<int>()); for (int i = 0; i < n; ++i) { blocks[i / blockSize].push_back(array[i]); } // Create a data structure to store the answers to the range queries. std::vector<int> answers; // Answer the range queries. for (const auto& query : queries) { int start = query.first; int end = query.second; int startBlock = start / blockSize; int endBlock = end / blockSize; if (startBlock == endBlock) { // If the query is contained within a single block. int answer = 0; for (int i = start; i <= end; ++i) { answer += array[i]; } answers.push_back(answer); } else { // If the query spans multiple blocks. // Partial sum in the start block int answer = 0; for (int i = start; i < (startBlock + 1) * blockSize; ++i) { answer += array[i]; } // Sum of complete blocks for (int i = startBlock + 1; i < endBlock; ++i) { answer += std::accumulate(blocks[i].begin(), blocks[i].end(), 0); } // Partial sum in the end block for (int i = endBlock * blockSize; i <= end; ++i) { answer += array[i]; } answers.push_back(answer); } } return answers;}int main() { // Create an input array. std::vector<int> array; std::srand(std::time(0)); for (int i = 1; i <= 100; ++i) { array.push_back(i); } // Create a vector of range queries. std::vector<std::pair<int, int>> queries; for (int i = 0; i < 10; ++i) { queries.push_back({std::rand() % 100, std::rand() % 100}); } // Answer the range queries using Mo's algorithm without update. std::vector<int> answersWithoutUpdate = moAlgorithmWithoutUpdate(array, queries); std::cout << "Answers without update:" << std::endl; for (int answer : answersWithoutUpdate) { std::cout << answer << std::endl; } return 0;} |
Python3
# Python Implementationimport randomimport mathdef mo_algorithm_without_update(array, queries): """ Answer range queries using Mo's algorithm without update. Args: array: The input array. queries: The range queries. Returns: The answers to the range queries. """ # Divide the input array into blocks of # size sqrt(N). block_size = int(math.sqrt(len(array))) blocks = [[] for _ in range(len(array) // block_size)] for i in range(len(array)): blocks[i // block_size].append(array[i]) # Create a data structure to store the # answers to the range queries. answers = [] # Answer the range queries. for query in queries: start, end = query start_block = start // block_size end_block = end // block_size if start_block == end_block: # If the query is contained within # a single block. answer = sum(array[start:end + 1]) else: # If the query spans multiple blocks. # Partial sum in the start block answer = sum(array[start:(start_block + 1) * block_size]) # Sum of complete blocks answer += sum(sum(blocks[start_block + 1:end_block], [])) # Partial sum in the end block answer += sum(array[end_block * block_size:end + 1]) answers.append(answer) return answers# Driver codedef main(): # Create an input array. array = [random.randint(0, 100) for _ in range(100)] # Create a list of range queries. queries = [] for _ in range(10): queries.append((random.randint(0, 99), random.randint(0, 99))) # Create a list of update operations. updates = [] for _ in range(5): updates.append((random.randint(0, 99), random.randint(0, 100))) # Answer the range queries using Mo's algorithm # without update. answers_without_update = mo_algorithm_without_update(array, queries) print("Answers without update:") for answer in answers_without_update: print(answer)if __name__ == "__main__": main() |
Output
Answers without update: 3308 439 179 378 681 428 4395 303 2907 480
Time Complexity: O(Q * sqrt(N))
Auxiliary Space: O(sqrt(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
