AntInLoop

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]