Crate mo_algorithm 

Mo’s algorithm for offline range queries.

Mo’s algorithm solves queries of the form “given a value array a, and a list of range queries [lo, hi), answer each query using only O(|hi - lo|) moves between consecutive queries (with O(1) amortized per move) once the queries have been reordered.

The classic instance is counting distinct elements in a range. This crate ships count_distinct_in_range, which handles that case directly:

use mo_algorithm::{count_distinct_in_range, Query};

let a = vec![1, 1, 2, 1, 3];
let queries = vec![Query { lo: 0, hi: 3 }, Query { lo: 2, hi: 5 }];
let answers = count_distinct_in_range(&a, &queries);
assert_eq!(answers, vec![2, 3]);

For more elaborate query types build your own solver using solve_blocked.

Structs

Query

A single query on a half-open interval [lo, hi).

Functions

count_distinct_in_range

Solve “number of distinct values in range” queries using Mo’s algorithm.

solve_blocked

Run a generic Mo’s algorithm over n elements answering queries.