797 Intermediate

797-range-minimum-query — Range Minimum Query (Sparse Table)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "797-range-minimum-query — Range Minimum Query (Sparse Table)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Range Minimum Query (RMQ) asks: given an array and a query `(l, r)`, what is the minimum element in `arr[l..=r]`? Key difference from OCaml: 1. **Immutability advantage**: Sparse Table's O(1) query relies on immutability; Rust's ownership system naturally prevents mutation after construction.

Tutorial

The Problem

Range Minimum Query (RMQ) asks: given an array and a query (l, r), what is the minimum element in arr[l..=r]? Naive O(n) per query is too slow for many applications. The Sparse Table data structure preprocesses the array in O(n log n) time to answer RMQ queries in O(1) using overlapping power-of-two ranges. RMQ is used in LCA (Lowest Common Ancestor) algorithms for trees, suffix array construction, and competitive programming.

🎯 Learning Outcomes

• Build a sparse table table[j][i] = index of minimum in arr[i..i+2^j]

• Use log precomputation log[i] = floor(log2(i)) for O(1) query dispatch

• Answer query(l, r) by overlapping two ranges of size 2^k where k = log[r-l+1]

• Understand why overlapping ranges are valid (minimum is idempotent: min(min(a,b), min(b,c)) = min(a,b,c))

• Know when Segment Trees (O(log n) query, O(log n) update) are preferred over Sparse Tables (O(1) query, immutable)

Code Example

#![allow(clippy::all)]
//! # Range Minimum Query (Sparse Table)

pub struct SparseTable {
    table: Vec<Vec<usize>>,
    log: Vec<usize>,
}

impl SparseTable {
    pub fn new(arr: &[i32]) -> Self {
        let n = arr.len();
        let k = (n as f64).log2().floor() as usize + 1;
        let mut table = vec![vec![0; n]; k];
        let mut log = vec![0; n + 1];
        for i in 2..=n {
            log[i] = log[i / 2] + 1;
        }
        for i in 0..n {
            table[0][i] = i;
        }
        for j in 1..k {
            for i in 0..=(n - (1 << j)) {
                let left = table[j - 1][i];
                let right = table[j - 1][i + (1 << (j - 1))];
                table[j][i] = if arr[left] <= arr[right] { left } else { right };
            }
        }
        Self { table, log }
    }

    pub fn query(&self, arr: &[i32], l: usize, r: usize) -> usize {
        let j = self.log[r - l + 1];
        let left = self.table[j][l];
        let right = self.table[j][r - (1 << j) + 1];
        if arr[left] <= arr[right] {
            left
        } else {
            right
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_rmq() {
        let arr = [1, 3, 2, 7, 9, 11];
        let st = SparseTable::new(&arr);
        assert_eq!(st.query(&arr, 0, 2), 0);
    }
}

(* Range Minimum Query — Sparse Table O(n log n) build, O(1) query *)

let build_sparse arr =
  let n = Array.length arr in
  let log2 = if n > 1 then int_of_float (log (float_of_int n) /. log 2.0) + 1 else 1 in
  let table = Array.init log2 (fun k ->
    Array.init n (fun i ->
      if k = 0 then arr.(i)
      else min max_int max_int (* filled below *)
    )
  ) in
  table.(0) <- Array.copy arr;
  for k = 1 to log2 - 1 do
    for i = 0 to n - (1 lsl k) do
      table.(k).(i) <- min table.(k-1).(i) table.(k-1).(i + (1 lsl (k-1)))
    done
  done;
  table

let query table l r =
  let len = r - l + 1 in
  let k   = int_of_float (log (float_of_int len) /. log 2.0) in
  min table.(k).(l) table.(k).(r - (1 lsl k) + 1)

let () =
  let arr   = [| 2; 4; 3; 1; 6; 7; 8; 9; 1; 7 |] in
  let table = build_sparse arr in
  Printf.printf "Array: ";
  Array.iter (fun x -> Printf.printf "%d " x) arr;
  print_newline ();
  Printf.printf "RMQ(0,9) = %d  (expect 1)\n" (query table 0 9);
  Printf.printf "RMQ(1,5) = %d  (expect 1)\n" (query table 1 5);
  Printf.printf "RMQ(2,4) = %d  (expect 1)\n" (query table 2 4);
  Printf.printf "RMQ(6,9) = %d  (expect 1)\n" (query table 6 9)

Key Differences

Immutability advantage: Sparse Table's O(1) query relies on immutability; Rust's ownership system naturally prevents mutation after construction.

Space: O(n log n) space for the sparse table vs. O(n) for a simple segment tree — a trade-off between query speed and memory.

RMQ vs other queries: Sparse tables work for any idempotent function (min, max, GCD); non-idempotent functions (sum) require segment trees instead.

Competitive programming: RMQ + LCA is a classic competitive programming combo; Rust is increasingly used in competitive programming for its speed and safety.

OCaml Approach

OCaml implements the sparse table with Array.make_matrix k n 0. The log precomputation uses a for loop over indices. OCaml's log2 function with int_of_float computes the floor log2. min is the stdlib comparison function. The query function is a two-line function selecting the minimum of two table entries. Segment trees (a related data structure) are common in OCaml competitive programming.

Full Source

#![allow(clippy::all)]
//! # Range Minimum Query (Sparse Table)

pub struct SparseTable {
    table: Vec<Vec<usize>>,
    log: Vec<usize>,
}

impl SparseTable {
    pub fn new(arr: &[i32]) -> Self {
        let n = arr.len();
        let k = (n as f64).log2().floor() as usize + 1;
        let mut table = vec![vec![0; n]; k];
        let mut log = vec![0; n + 1];
        for i in 2..=n {
            log[i] = log[i / 2] + 1;
        }
        for i in 0..n {
            table[0][i] = i;
        }
        for j in 1..k {
            for i in 0..=(n - (1 << j)) {
                let left = table[j - 1][i];
                let right = table[j - 1][i + (1 << (j - 1))];
                table[j][i] = if arr[left] <= arr[right] { left } else { right };
            }
        }
        Self { table, log }
    }

    pub fn query(&self, arr: &[i32], l: usize, r: usize) -> usize {
        let j = self.log[r - l + 1];
        let left = self.table[j][l];
        let right = self.table[j][r - (1 << j) + 1];
        if arr[left] <= arr[right] {
            left
        } else {
            right
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_rmq() {
        let arr = [1, 3, 2, 7, 9, 11];
        let st = SparseTable::new(&arr);
        assert_eq!(st.query(&arr, 0, 2), 0);
    }
}

(* Range Minimum Query — Sparse Table O(n log n) build, O(1) query *)

let build_sparse arr =
  let n = Array.length arr in
  let log2 = if n > 1 then int_of_float (log (float_of_int n) /. log 2.0) + 1 else 1 in
  let table = Array.init log2 (fun k ->
    Array.init n (fun i ->
      if k = 0 then arr.(i)
      else min max_int max_int (* filled below *)
    )
  ) in
  table.(0) <- Array.copy arr;
  for k = 1 to log2 - 1 do
    for i = 0 to n - (1 lsl k) do
      table.(k).(i) <- min table.(k-1).(i) table.(k-1).(i + (1 lsl (k-1)))
    done
  done;
  table

let query table l r =
  let len = r - l + 1 in
  let k   = int_of_float (log (float_of_int len) /. log 2.0) in
  min table.(k).(l) table.(k).(r - (1 lsl k) + 1)

let () =
  let arr   = [| 2; 4; 3; 1; 6; 7; 8; 9; 1; 7 |] in
  let table = build_sparse arr in
  Printf.printf "Array: ";
  Array.iter (fun x -> Printf.printf "%d " x) arr;
  print_newline ();
  Printf.printf "RMQ(0,9) = %d  (expect 1)\n" (query table 0 9);
  Printf.printf "RMQ(1,5) = %d  (expect 1)\n" (query table 1 5);
  Printf.printf "RMQ(2,4) = %d  (expect 1)\n" (query table 2 4);
  Printf.printf "RMQ(6,9) = %d  (expect 1)\n" (query table 6 9)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_rmq() {
        let arr = [1, 3, 2, 7, 9, 11];
        let st = SparseTable::new(&arr);
        assert_eq!(st.query(&arr, 0, 2), 0);
    }
}

Deep Comparison

OCaml vs Rust: Range Minimum Query

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement range_gcd_query(arr, l, r) -> u64 using a sparse table (GCD is idempotent: gcd(gcd(a,b), gcd(b,c)) = gcd(a,b,c)).

Implement an alternative SparseTable that returns the actual value rather than the index, and compare its ergonomics for the min/max use case.

Implement a Segment Tree that supports both range minimum queries AND point updates in O(log n), demonstrating when it's preferred over the Sparse Table.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust