Beberapa persoalan range query tidak bisa diselesaikan dengan segment tree atau Fenwick karena operasinya tidak asosiatif atau memerlukan state kompleks (mis. count distinct elemen, sum of squares of frequency). Untuk skenario offline (semua query diketahui di awal) tanpa update, Mo’s algorithm memberi solusi O((n+q)√n) dengan teknik yang elegan: urutkan query berdasarkan blok √n, dan geser dua pointer L dan R secara incremental antar query. Selain Mo, terdapat juga sqrt decomposition biasa dan Hilbert curve Mo yang lebih optimal. Pada Chapter ini kita membedah Mo’s algorithm dengan implementasi penuh, menjawab query “sum of value × freq²” yang sulit dilakukan dengan struktur data biasa.

Aturan: Offline Range Query Tanpa Update #

Diberikan array A[0..n-1] statis (tidak ada update) dan q query berupa range [l, r]. Untuk setiap query, hitung agregat yang tidak trivial. Contoh:

  • Count distinct elemen di [l, r].
  • Sum of freq(x)² × x untuk setiap nilai x di [l, r].
  • Number of inversions in subarray [l, r].
  • Mode (elemen paling sering muncul) di [l, r].

Untuk operasi-operasi ini, segment tree lazy tidak langsung apply karena tidak monoid sederhana. Mo’s algorithm menyelesaikannya dalam O((n+q)√n) bila add/remove elemen O(1).

Mekanisme: Sort by Block + Slide Two Pointers #

Ide Mo:

  1. Bagi array menjadi blok ukuran B = √n. Setiap indeks i masuk blok i / B.
  2. Sortir query dengan komparator:
    • Blok dari L terkecil ke terbesar.
    • Dalam blok yang sama, sortir R naik (atau turun untuk blok ganjil — optimasi Hilbert-like).
  3. Proses query secara berurutan, geser pointer cur_l dan cur_r dari query sebelumnya ke query saat ini:
    • Expand: add(--cur_l) atau add(++cur_r).
    • Shrink: remove(cur_l++) atau remove(cur_r--).
  4. Total pergerakan pointer = O(n√n) (lihat analisis di bawah).

Analisis Kompleksitas #

Misal n elemen, q query, B = √n:

  • Pergerakan R: dalam satu blok L, R monoton naik. Total gerakan R per blok = O(n). Ada n/B = √n blok → total R movement = O(n√n).
  • Pergerakan L: dalam satu query, L bergerak paling jauh B = √n. Total L movement per blok = O(qB/√n × √n) = O(q√n)? Sebenarnya total = O(q × B) = O(q√n).
  • Total: O((n + q)√n).

Bila q ≈ n, total = O(n^1.5). Untuk n = 10^5, ini sekitar 3 × 10^7 operasi — bisa dijalankan.

Implementasi Mo’s Algorithm #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

// Mo's algorithm: process offline range queries in sqrt(n) blocks.
// Adding/removing element O(1) amortized -> total O((n+q) * sqrt(n)).

int block_size;
std::vector<int> arr;
long long current_answer = 0;
int freq[100];  // assume values in [0, 100)

void add(int idx) {
    int v = arr[idx];
    int old = freq[v];
    // contribution: sum of (freq(x))^2 * x for each distinct value x
    current_answer -= (long long)old * old * v;
    freq[v]++;
    int now = freq[v];
    current_answer += (long long)now * now * v;
}

void remove(int idx) {
    int v = arr[idx];
    int old = freq[v];
    current_answer -= (long long)old * old * v;
    freq[v]--;
    int now = freq[v];
    current_answer += (long long)now * now * v;
}

struct Query {
    int l, r, idx;
    long long ans;
};

int main() {
    arr = {1, 2, 1, 3, 1, 2, 1, 4, 2, 1};
    int n = arr.size();
    std::vector<Query> queries = {
        {0, 4, 0, 0}, {1, 5, 1, 0}, {2, 7, 2, 0}, {0, 9, 3, 0}, {3, 6, 4, 0}
    };

    block_size = std::max(1, (int)std::sqrt((double)n));

    // Sort queries: by block of L, then by R (alternating for even blocks - hilbert optimization)
    auto mo_cmp = [&](const Query& a, const Query& b) {
        int ba = a.l / block_size;
        int bb = b.l / block_size;
        if (ba != bb) return ba < bb;
        // Hilbert-like: alternasi naik/turun R untuk blok genap/ganjil
        if (ba % 2 == 0) return a.r < b.r;
        return a.r > b.r;
    };

    std::sort(queries.begin(), queries.end(), mo_cmp);

    int cur_l = 0, cur_r = -1;
    for (auto& Q : queries) {
        while (cur_l > Q.l) add(--cur_l);
        while (cur_r < Q.r) add(++cur_r);
        while (cur_l < Q.l) remove(cur_l++);
        while (cur_r > Q.r) remove(cur_r--);
        Q.ans = current_answer;
    }

    // Restore original order
    std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.idx < b.idx;
    });

    for (const auto& Q : queries) {
        std::cout << "Q[" << Q.idx << "] range [" << Q.l << "," << Q.r << "] = " << Q.ans << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Q[0] range [0,4] = 14
Q[1] range [1,5] = 15
Q[2] range [2,7] = 18
Q[3] range [0,9] = 50
Q[4] range [3,6] = 9

Bedah Kode Baris-per-Baris #

  1. block_size = sqrt(n): ukuran blok optimal untuk Mo’s. Bila q » n, gunakan n / sqrt(q) (block size disesuaikan).
  2. freq[100]: frequency counter untuk setiap nilai (asumsi nilai di [0, 100)). Untuk nilai besar, koordinat compress dulu ke [0, n) sebelum Mo.
  3. add(idx): tambahkan arr[idx] ke jendela saat ini. Update current_answer dengan kontribusi nilai v = arr[idx]:
    • Sebelum add: kontribusi v adalah freq[v]² × v (lama).
    • Setelah freq[v]++: kontribusi baru (freq[v]+1)² × v.
    • Update current_answer -= old² × v; freq[v]++; current_answer += new² × v;.
  4. remove(idx): kebalikan add. Kurangi freq[v], update kontribusi.
  5. mo_cmp: komparator sort. Pertama sort by blok L / block_size. Dalam blok yang sama, bila blok genap sort R naik, bila ganjil sort R turun. Trik alternasi arah menghemat pergerakan R (saat pindah blok genap ke ganjil, R tidak perlu reset ke 0 — lanjut dari posisi terakhir).
  6. while (cur_l > Q.l) add(--cur_l): expand jendela ke kiri. --cur_l dulu (pindah ke kiri), baru add elemen baru.
  7. while (cur_r < Q.r) add(++cur_r): expand jendela ke kanan.
  8. while (cur_l < Q.l) remove(cur_l++): shrink dari kiri. remove(cur_l) dulu (elemen di cur_l keluar), baru cur_l++.
  9. while (cur_r > Q.r) remove(cur_r--): shrink dari kanan.
  10. Urutan expand sebelum shrink penting: bila jendela baru lebih besar dari lama, expand dulu agar tidak pernah kosong. Bila shrink dulu, bisa terjadi cur_l > cur_r (jendela kosong) yang break invariant add/remove.
  11. Q.ans = current_answer: jawaban query = state saat ini.
  12. Restore original order: sort kembali by idx agar output sesuai urutan query input.
  13. Verifikasi:
    • arr = [1,2,1,3,1,2,1,4,2,1].
    • Q[0] range [0,4] = arr[0..4] = [1,2,1,3,1]. freq: 1→3, 2→1, 3→1. Sum = 3²×1 + 1²×2 + 1²×3 = 9+2+3 = 14. ✓
    • Q[1] range [1,5] = [2,1,3,1,2]. freq: 1→2, 2→2, 3→1. Sum = 4×1 + 4×2 + 1×3 = 4+8+3 = 15. ✓
    • Q[2] range [2,7] = [1,3,1,2,1,4]. freq: 1→3, 2→1, 3→1, 4→1. Sum = 9×1 + 1×2 + 1×3 + 1×4 = 9+2+3+4 = 18. ✓
    • Q[3] range [0,9] = all. freq: 1→5, 2→3, 3→1, 4→1. Sum = 25×1 + 9×2 + 1×3 + 1×4 = 25+18+3+4 = 50. ✓
    • Q[4] range [3,6] = [3,1,2,1]. freq: 1→2, 2→1, 3→1. Sum = 4×1 + 1×2 + 1×3 = 4+2+3 = 9. ✓

Variasi: Hilbert Curve Mo #

Hilbert curve Mo menggunakan urutan Hilbert untuk sort query — kompleksitas O((n+q)√n) tetapi konstanta lebih kecil (~2-3× lebih cepat). Ide: petakan setiap (l, r) ke nilai Hilbert curve, sort by nilai Hilbert. Hilbert curve menjaga locality: query yang berdekatan dalam 2D memiliki jarak kecil dalam 1D, mengurangi pergerakan pointer.

cpp 
// Hilbert order function
long long hilbertOrder(int x, int y, int pow = 21, int rotate = 0) {
    if (pow == 0) return 0;
    int hpow = 1 << (pow - 1);
    int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
    seg = (seg + rotate) & 3;
    static const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    long long sub = hilbertOrder(nx, ny, pow - 1, nrot);
    return (seg << (2 * (pow - 1))) | sub;
}
// Sort by hilbertOrder(l, r)

Sqrt Decomposition Biasa #

Untuk masalah dengan update dan query, sqrt decomposition biasa juga berguna:

  • Bagi array menjadi blok ukuran B = √n.
  • Setiap blok menyimpan aggregate (sum, min, sorted list, dsb.).
  • Point update: update elemen + aggregate blok. O(1) atau O(log B).
  • Range query: scan penuh blok-blok dalam range + elemen-elemen di blok parsial. O(B + n/B) = O(√n).
  • Range update: lazy tag per blok. O(√n).

Lebih lambat dari segment tree lazy (O(√n) vs O(log n)) tetapi lebih mudah diimplementasi untuk operasi kompleks.

Kompleksitas #

TeknikPreprocessQueryUpdateUse Case
Sparse tableO(n log n)O(1)—Static, idempotent
Segment treeO(n)O(log n)O(log n)Dynamic, monoid
FenwickO(n)O(log n)O(log n)Dynamic, prefix-friendly
Mo’s algorithm—O((n+q)√n) total—Static, offline, non-monoid
Sqrt decompositionO(n)O(√n)O(√n)Dynamic, complex ops

Ringkasan #

  • Mo’s algorithm = sort query by block + slide two pointers. Total O((n+q)√n).
  • add/remove harus O(1) — bukan monoid sederhana (count distinct, sum freq², mode, inversion count).
  • Optimasi: alternasi arah R untuk blok genap/ganjil menghemat gerakan pointer.
  • Hilbert curve Mo: kompleksitas sama, konstanta lebih kecil ~2-3×.
  • Sqrt decomposition biasa: untuk update + query dengan operasi kompleks. O(√n) per operasi.
  • Pilihan: Mo bila offline static, segment tree bila online dynamic, sparse table bila static idempotent.