Skip to content

Data Structures -> Mo's Algorithm

Offline range-query ordering for static arrays when one current active interval can be updated cheaply by moving endpoints.

  • Topic slug: data-structures/mos-algorithm
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 5
  • Curated external problems: 4

Microtopics

  • block-ordering
  • snake-order
  • current-range
  • frequency-maintenance
  • symmetric-add-remove
  • sqrt-decomposition-order

Learning Sources

Source Type
cp-algorithms sqrt decomposition / Mo's algorithm Reference
OI Wiki Mo's algorithm intro Reference
USACO Guide square root decomposition Reference

Practice Sources

Source Type
Codeforces problemset Practice
Library Checker Static Range Count Distinct Practice
SPOJ DQUERY Practice

Repo Companion Material

Material Type
Mo's hot sheet quick reference
Mo starter route starter route
Powerful Array note anchor note
Offline Tricks tutorial compare point
Distinct Values Queries note compare point

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Powerful Array Codeforces Hard Frequency Maintenance Query-Heavy; Data-Structure-Heavy Offline Query Ordering; Current Range Invariant Range-Frequency; Offline A famous Mo benchmark where the current answer is one frequency-weighted score and add/remove are true local updates.

Practice

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Static Range Count Distinct Library Checker Hard - Query-Heavy; Data-Structure-Heavy Mo's Algorithm; Frequency Counts; Coordinate Compression Distinct-Count; Offline An official verifier-style Mo benchmark once ordinary current-range maintenance is trusted.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
D-query SPOJ Hard Classic Query-Heavy; Data-Structure-Heavy Mo's Algorithm; Frequency Counts; Coordinate Compression Distinct-Count; Offline Range Queries The classic static distinct-count Mo problem and a good second rep after one frequency-score benchmark.

Bridge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Distinct Values Queries CSES Hard Compare Point Query-Heavy; Compare-Point Mo's Algorithm; Offline Sweeps; Frequency Counts Distinct-Count; Offline A deliberate compare point: Mo works, but the monotone right-endpoint sweep is cleaner and should still be preferred.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
POWERFULARRAY Powerful Array primary hard - Note Code

Regeneration

python3 scripts/generate_problem_catalog.py