Mo's Algorithm (Offline Range Queries) Code Implementations
Complete Mo's Algorithm (Offline Range Queries) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Mo's Algorithm (Offline Range Queries) Guide ยท Launch Interactive Visualizer
C++ Implementation
// Mo's Algorithm in C++ (Range Sum Query)
#include <bits/stdc++.h>
using namespace std;
struct Query {
int l, r, idx;
int block;
bool operator<(const Query &other) const {
if (block != other.block)
return block < other.block;
return (block & 1) ? (r > other.r) : (r < other.r);
}
};
vector<int> mosAlgorithm(const vector<int> &arr, vector<Query> &queries) {
int n = arr.size();
int q = queries.size();
int blockSize = sqrt(n);
for (auto &query : queries) {
query.block = query.l / blockSize;
}
sort(queries.begin(), queries.end());
vector<int> answers(q);
int currL = 0, currR = -1, currSum = 0;
auto add = [&](int i) { currSum += arr[i]; };
auto remove = [&](int i) { currSum -= arr[i]; };
for (auto &q : queries) {
while (currL > q.l) add(--currL);
while (currR < q.r) add(++currR);
while (currL < q.l) remove(currL++);
while (currR > q.r) remove(currR--);
answers[q.idx] = currSum;
}
return answers;
}
// Example usage
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
vector<Query> queries = {{1, 3, 0}, {0, 4, 1}};
vector<int> res = mosAlgorithm(arr, queries);
for (int ans : res) cout << ans << " ";
return 0; // Output: 9 15
}JAVA Implementation
// Mo's Algorithm in Java (Range Sum Example)
import java.util.*;
class Query implements Comparable<Query> {
int l, r, idx;
int blockSize;
Query(int l, int r, int idx, int blockSize) {
this.l = l;
this.r = r;
this.idx = idx;
this.blockSize = blockSize;
}
public int compareTo(Query other) {
int blockA = this.l / blockSize;
int blockB = other.l / blockSize;
if (blockA != blockB)
return blockA - blockB;
return (blockA % 2 == 0) ? (this.r - other.r) : (other.r - this.r);
}
}
public class MoAlgorithm {
public static int[] mosAlgorithm(int[] arr, Query[] queries) {
int n = arr.length;
int q = queries.length;
int blockSize = (int)Math.sqrt(n);
for (Query query : queries) query.blockSize = blockSize;
Arrays.sort(queries);
int[] answers = new int[q];
int currL = 0, currR = -1, currSum = 0;
for (Query qObj : queries) {
while (currL > qObj.l) currSum += arr[--currL];
while (currR < qObj.r) currSum += arr[++currR];
while (currL < qObj.l) currSum -= arr[currL++];
while (currR > qObj.r) currSum -= arr[currR--];
answers[qObj.idx] = currSum;
}
return answers;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
Query[] queries = {
new Query(1, 3, 0, 0),
new Query(0, 4, 1, 0)
};
int[] ans = mosAlgorithm(arr, queries);
System.out.println(Arrays.toString(ans)); // [9, 15]
}
}JAVASCRIPT Implementation
// Mo's Algorithm (Range Sum Query Example) in JavaScript
class Query {
constructor(l, r, idx) {
this.l = l;
this.r = r;
this.idx = idx;
}
}
function mosAlgorithm(arr, queries) {
const n = arr.length;
const q = queries.length;
const blockSize = Math.floor(Math.sqrt(n));
const answer = new Array(q);
const freq = {};
// Sort queries by Mo's ordering
queries.sort((a, b) => {
const blockA = Math.floor(a.l / blockSize);
const blockB = Math.floor(b.l / blockSize);
return blockA !== blockB
? blockA - blockB
: (blockA % 2 === 0 ? a.r - b.r : b.r - a.r);
});
let currL = 0, currR = -1, currSum = 0;
const add = (i) => {
currSum += arr[i];
};
const remove = (i) => {
currSum -= arr[i];
};
for (const query of queries) {
while (currL > query.l) add(--currL);
while (currR < query.r) add(++currR);
while (currL < query.l) remove(currL++);
while (currR > query.r) remove(currR--);
answer[query.idx] = currSum;
}
return answer;
}
// Example usage
const arr = [1, 2, 3, 4, 5];
const queries = [
new Query(1, 3, 0),
new Query(0, 4, 1)
];
console.log(mosAlgorithm(arr, queries)); // [9, 15]
PYTHON Implementation
# Mo's Algorithm (Range Sum Query Example) in Python
import math
class Query:
def __init__(self, l, r, idx):
self.l = l
self.r = r
self.idx = idx
def mos_algorithm(arr, queries):
n = len(arr)
block_size = int(math.sqrt(n))
answers = [0] * len(queries)
queries.sort(key=lambda q: (
q.l // block_size,
q.r if (q.l // block_size) % 2 == 0 else -q.r
))
curr_l, curr_r, curr_sum = 0, -1, 0
def add(i):
nonlocal curr_sum
curr_sum += arr[i]
def remove(i):
nonlocal curr_sum
curr_sum -= arr[i]
for q in queries:
while curr_l > q.l:
curr_l -= 1
add(curr_l)
while curr_r < q.r:
curr_r += 1
add(curr_r)
while curr_l < q.l:
remove(curr_l)
curr_l += 1
while curr_r > q.r:
remove(curr_r)
curr_r -= 1
answers[q.idx] = curr_sum
return answers
# Example usage
arr = [1, 2, 3, 4, 5]
queries = [Query(1, 3, 0), Query(0, 4, 1)]
print(mos_algorithm(arr, queries)) # Output: [9, 15]