Mo's Algorithm
(algo/offline/mo.hpp)

• View this file on GitHub
• Last update: 2026-07-07 21:49:48+09:00
• Include: #include "algo/offline/mo.hpp"

Overview

Mo reorders static range queries so a maintained half-open interval changes only a small number of positions between consecutive queries.

Use it when:

• every query is known before processing begins,
• the array does not change,
• one element can be inserted or erased from the maintained answer efficiently.

Basic API

m1une::algo::Mo mo(n);
int id = mo.add_query(left, right);
mo.run(add, remove, answer);

Queries use zero-based half-open intervals [left, right). add_query returns an insertion-order query ID. During run, answer(query_id) is called when the maintained state represents exactly that query’s range.

For statistics whose update is the same on both sides, use:

mo.run(add, remove, answer);

Both add(index) and remove(index) receive an array index.

Directional Updates

Some statistics depend on which endpoint moves. Inversion counting is a common example: adding an element to the left counts smaller existing elements, while adding one to the right counts larger existing elements.

Use the full overload:

mo.run(
    add_left,
    add_right,
    remove_left,
    remove_right,
    answer
);

Every callback receives the index being inserted or erased.

Methods

Method	Description	Complexity
Mo(int n)	Creates a query collection for an array of length n.	$O(1)$
add_query(l, r)	Adds [l, r) and returns its query ID.	Amortized $O(1)$
query_count()	Returns the number of queries.	$O(1)$
queries()	Returns all queries in insertion order.	$O(1)$
order(block_size)	Returns query IDs in processing order.	$O(Q\log Q)$
run(...)	Processes all queries.	See below
reserve(q)	Reserves storage for q queries.	$O(Q)$
clear()	Removes all queries while retaining array length.	$O(Q)$

order and run choose a block size automatically when block_size <= 0. Passing a positive value allows problem-specific tuning. Right endpoints are sorted in alternating directions between adjacent left blocks.

With $O(F)$ insertion and deletion callbacks, the usual complexity is $O((N+Q)\sqrt{Q}\,F + Q\log Q)$ using the automatically selected block size. The exact number of endpoint movements depends on the query distribution.

Example

This computes the number of distinct values in every query:

#include "algo/offline/mo.hpp"

#include <vector>

int main() {
    std::vector<int> values = {1, 2, 1, 3};
    m1une::algo::Mo mo(int(values.size()));
    mo.add_query(0, 3);
    mo.add_query(1, 4);

    std::vector<int> frequency(4);
    std::vector<int> result(mo.query_count());
    int distinct = 0;

    mo.run(
        [&](int index) {
            if (frequency[values[index]]++ == 0) distinct++;
        },
        [&](int index) {
            if (--frequency[values[index]] == 0) distinct--;
        },
        [&](int query_id) {
            result[query_id] = distinct;
        }
    );
}

Required by

• Algorithms All (algo/all.hpp)
• Offline Algorithms All (algo/offline/all.hpp)
• Graph All (graph/all.hpp)
• Tree All (graph/tree/all.hpp)
• Mo on Tree (graph/tree/mo_on_tree.hpp)

Verified with

• verify/algo/offline/mo.test.cpp
• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp
• verify/graph/tree/mo_on_tree.test.cpp
• verify/graph/tree/tree_algorithms.test.cpp

Code

#ifndef M1UNE_ALGO_OFFLINE_MO_HPP
#define M1UNE_ALGO_OFFLINE_MO_HPP 1

#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <vector>

namespace m1une {
namespace algo {

// Offline Mo's algorithm for half-open array ranges.
struct Mo {
    struct Query {
        int left;
        int right;
        int id;
    };

   private:
    int _n;
    std::vector<Query> _queries;

   public:
    Mo() : _n(0) {}

    explicit Mo(int n) : _n(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _queries.empty();
    }

    const std::vector<Query>& queries() const {
        return _queries;
    }

    void reserve(int query_capacity) {
        assert(0 <= query_capacity);
        _queries.reserve(query_capacity);
    }

    void clear() {
        _queries.clear();
    }

    // Adds [left, right) and returns its insertion-order ID.
    int add_query(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        int id = query_count();
        _queries.push_back(Query{left, right, id});
        return id;
    }

    // Returns query IDs in Mo order. A non-positive block size selects one
    // automatically.
    std::vector<int> order(int block_size = 0) const {
        int query_size = query_count();
        std::vector<int> result(query_size);
        std::iota(result.begin(), result.end(), 0);
        if (query_size == 0) return result;

        if (block_size <= 0) {
            block_size = std::max(1, int(_n / std::sqrt(static_cast<double>(query_size))));
        }

        std::sort(result.begin(), result.end(), [&](int first, int second) {
            const Query& a = _queries[first];
            const Query& b = _queries[second];
            int first_block = a.left / block_size;
            int second_block = b.left / block_size;
            if (first_block != second_block) {
                return first_block < second_block;
            }
            if (first_block & 1) return a.right > b.right;
            return a.right < b.right;
        });
        return result;
    }

    // Maintains [left, right). Each movement callback receives the array index
    // being inserted or erased. `answer(query_id)` stores or reports a result.
    template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight, class Answer>
    void run(AddLeft add_left, AddRight add_right, RemoveLeft remove_left, RemoveRight remove_right, Answer answer,
             int block_size = 0) const {
        int left = 0;
        int right = 0;
        for (int query_index : order(block_size)) {
            const Query& query = _queries[query_index];
            while (query.left < left) add_left(--left);
            while (right < query.right) add_right(right++);
            while (left < query.left) remove_left(left++);
            while (query.right < right) remove_right(--right);
            answer(query.id);
        }
    }

    // Convenience overload for statistics whose update is independent of
    // which side moves.
    template <class Add, class Remove, class Answer>
    void run(Add add, Remove remove, Answer answer, int block_size = 0) const {
        run(add, add, remove, remove, answer, block_size);
    }
};

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_OFFLINE_MO_HPP

#line 1 "algo/offline/mo.hpp"



#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <vector>

namespace m1une {
namespace algo {

// Offline Mo's algorithm for half-open array ranges.
struct Mo {
    struct Query {
        int left;
        int right;
        int id;
    };

   private:
    int _n;
    std::vector<Query> _queries;

   public:
    Mo() : _n(0) {}

    explicit Mo(int n) : _n(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _queries.empty();
    }

    const std::vector<Query>& queries() const {
        return _queries;
    }

    void reserve(int query_capacity) {
        assert(0 <= query_capacity);
        _queries.reserve(query_capacity);
    }

    void clear() {
        _queries.clear();
    }

    // Adds [left, right) and returns its insertion-order ID.
    int add_query(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        int id = query_count();
        _queries.push_back(Query{left, right, id});
        return id;
    }

    // Returns query IDs in Mo order. A non-positive block size selects one
    // automatically.
    std::vector<int> order(int block_size = 0) const {
        int query_size = query_count();
        std::vector<int> result(query_size);
        std::iota(result.begin(), result.end(), 0);
        if (query_size == 0) return result;

        if (block_size <= 0) {
            block_size = std::max(1, int(_n / std::sqrt(static_cast<double>(query_size))));
        }

        std::sort(result.begin(), result.end(), [&](int first, int second) {
            const Query& a = _queries[first];
            const Query& b = _queries[second];
            int first_block = a.left / block_size;
            int second_block = b.left / block_size;
            if (first_block != second_block) {
                return first_block < second_block;
            }
            if (first_block & 1) return a.right > b.right;
            return a.right < b.right;
        });
        return result;
    }

    // Maintains [left, right). Each movement callback receives the array index
    // being inserted or erased. `answer(query_id)` stores or reports a result.
    template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight, class Answer>
    void run(AddLeft add_left, AddRight add_right, RemoveLeft remove_left, RemoveRight remove_right, Answer answer,
             int block_size = 0) const {
        int left = 0;
        int right = 0;
        for (int query_index : order(block_size)) {
            const Query& query = _queries[query_index];
            while (query.left < left) add_left(--left);
            while (right < query.right) add_right(right++);
            while (left < query.left) remove_left(left++);
            while (query.right < right) remove_right(--right);
            answer(query.id);
        }
    }

    // Convenience overload for statistics whose update is independent of
    // which side moves.
    template <class Add, class Remove, class Answer>
    void run(Add add, Remove remove, Answer answer, int block_size = 0) const {
        run(add, add, remove, remove, answer, block_size);
    }
};

}  // namespace algo
}  // namespace m1une

Back to top page