Coordinate Compression

Banyak soal kompetisi memberi nilai hingga 10⁹ atau bahkan 10¹⁸, padahal jumlah elemen hanya 10⁵. Membangun segment tree atau Fenwick tree berukuran 10⁹ mustahil karena batas memori. Coordinate compression menyelesaikan ini: kita petakan setiap nilai unik ke indeks berurutan 0..k-1 di mana k ≤ n. Setelah pemetaan, struktur data berukuran O(n) tetap layak. Pada Chapter ini kita akan mempelajari implementasi coordinate compression di C++ dan aplikasinya pada soal “count inversions” dan “range sum query dengan koordinat besar”.

Intuisi: Hanya Yang Muncul Adalah Penting #

Aturan #

Diberikan array a berisi nilai v_i (boleh sangat besar). Buat pemetaan compress(v) sehingga:

compress(v) adalah integer 0..k-1 di mana k = jumlah nilai unik di a.
Untuk u < v di antara nilai-nilai yang muncul, compress(u) < compress(v) (preserves order).
Untuk nilai v yang tidak muncul di a, compress(v) tidak terdefinisi (atau mengembalikan posisi insert).

Mekanisme: Sort + Unique #

Langkah compression:

Salin array ke sorted_a, urutkan.
Hilangkan duplikat dengan std::unique.
Untuk query compress(v), gunakan std::lower_bound pada sorted_a.

flowchart LR A["a = {100, 50, 200, 50, 100}"] --> B["sort: {50, 50, 100, 100, 200}"] B --> C["unique: {50, 100, 200}"] C --> D["compress(100) = 1"] C --> E["compress(50) = 0"] C --> F["compress(200) = 2"]

Kode: Fungsi Coordinate Compression #

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

class CoordinateCompressor {
public:
    explicit CoordinateCompressor(const std::vector<long long>& values) {
        sorted_ = values;
        std::sort(sorted_.begin(), sorted_.end());
        sorted_.erase(std::unique(sorted_.begin(), sorted_.end()), sorted_.end());
    }

    int compress(long long v) const {
        return static_cast<int>(
            std::lower_bound(sorted_.begin(), sorted_.end(), v) - sorted_.begin()
        );
    }

    int size() const { return static_cast<int>(sorted_.size()); }

    long long decompress(int idx) const { return sorted_[idx]; }

private:
    std::vector<long long> sorted_;
};

int main() {
    std::vector<long long> a = {100, 50, 200, 50, 100, 1'000'000'000'000LL, 200};
    CoordinateCompressor cc(a);
    std::cout << "Jumlah nilai unik: " << cc.size() << '\n';
    for (long long v : a) {
        std::cout << "compress(" << v << ") = " << cc.compress(v) << '\n';
    }
    std::cout << "decompress(2) = " << cc.decompress(2) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Jumlah nilai unik: 4
compress(100) = 1
compress(50) = 0
compress(200) = 2
compress(50) = 0
compress(100) = 1
compress(1000000000000) = 3
compress(200) = 2
decompress(2) = 200

Baris std::sort(sorted_.begin(), sorted_.end());: urutkan semua nilai. O(n log n).
Baris sorted_.erase(std::unique(...), sorted_.end());: hapus duplikat. std::unique menggeser elemen unik ke depan dan mengembalikan iterator ke akhir baru; erase memotong sisa.
Baris return std::lower_bound(...) - sorted_.begin();: lower_bound memberi iterator ke elemen pertama ≥ v — karena v pasti ada (nilai-nilai berasal dari a), indeksnya adalah posisi terurut. O(log n).
Baris long long decompress(int idx): kembalikan nilai asli dari indeks terkompresi. Berguna untuk display atau debugging.
Hasil compress(100) = 1: nilai 100 muncul di posisi terurut kedua (indeks 1) pada {50, 100, 200, 10^12}. Sesuai.
Hasil compress(10^12) = 3: nilai sangat besar, tetap mendapat indeks valid. Inilah inti coordinate compression.

Aplikasi 1: Count Inversions via BIT #

Aturan #

Diberikan array a berukuran n (nilai bisa sangat besar), hitung jumlah pasangan (i, j) dengan i < j dan a[i] > a[j]. Solusi naif O(n²). Dengan coordinate compression + Fenwick tree: O(n log n).

Mekanisme: Iterasi kanan, hitung kiri #

Untuk setiap j dari kiri ke kanan, hitung berapa elemen di a[0..j-1] yang lebih besar dari a[j]. Total = jumlah inversions. Setelah compression, kita bisa pakai BIT berukuran k (≤ n) alih-alih max(a).

Kode: Count Inversions #

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

class BIT {
public:
    explicit BIT(int n) : tree_(n + 1, 0) {}
    void add(int i, long long v) {
        for (++i; i < (int)tree_.size(); i += i & (-i)) tree_[i] += v;
    }
    long long sum(int i) const {  // prefix [0..i]
        long long s = 0;
        for (++i; i > 0; i -= i & (-i)) s += tree_[i];
        return s;
    }
private:
    std::vector<long long> tree_;
};

long long count_inversions(const std::vector<long long>& a) {
    int n = static_cast<int>(a.size());
    std::vector<long long> sorted_a = a;
    std::sort(sorted_a.begin(), sorted_a.end());
    sorted_a.erase(std::unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
    auto compress = [&](long long v) {
        return static_cast<int>(
            std::lower_bound(sorted_a.begin(), sorted_a.end(), v) - sorted_a.begin()
        );
    };
    int k = static_cast<int>(sorted_a.size());
    BIT bit(k);
    long long inv = 0;
    for (int j = 0; j < n; ++j) {
        int idx = compress(a[j]);
        // Jumlah elemen > a[j] = total - prefix(idx)
        long long total_so_far = j;
        long long le_idx = bit.sum(idx);  // elemen dengan compress <= idx
        inv += total_so_far - le_idx;
        bit.add(idx, 1);
    }
    return inv;
}

int main() {
    std::vector<long long> a = {5, 2, 6, 1, 3, 4};
    std::cout << "inversions = " << count_inversions(a) << '\n';
    std::vector<long long> b = {1, 2, 3, 4, 5};
    std::cout << "inversions = " << count_inversions(b) << '\n';
    std::vector<long long> c = {5, 4, 3, 2, 1};
    std::cout << "inversions = " << count_inversions(c) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
inversions = 8
inversions = 0
inversions = 10

Class BIT: Fenwick tree standar. add(i, v) menambah v ke indeks i; sum(i) menjumlahkan [0..i].
Lambda compress(v): gunakan sorted_a untuk mencari indeks terkompresi. Karena lambda capture sorted_a by reference, biaya kecil.
Baris int k = static_cast<int>(sorted_a.size());: ukuran BIT = jumlah nilai unik, bukan max(a).
Baris long long le_idx = bit.sum(idx);: jumlah elemen yang sudah dimasukkan ke BIT dengan indeks ≤ idx — yaitu elemen yang nilainya ≤ a[j].
Baris inv += total_so_far - le_idx;: elemen yang lebih besar dari a[j] = total elemen sebelumnya - elemen yang ≤ a[j]. Inilah kontribusi j ke total inversions.
Baris bit.add(idx, 1);: masukkan a[j] ke BIT untuk iterasi berikutnya.
Hasil 8 untuk {5,2,6,1,3,4}: inversions = (5,2), (5,1), (5,3), (5,4), (2,1), (6,1), (6,3), (6,4) = 8. Sesuai.
Hasil 10 untuk {5,4,3,2,1} (sorted terbalik): n=5, maksimum inversions = n·(n-1)/2 = 10. Sesuai.

Aplikasi 2: Range Query dengan Koordinat Besar #

Aturan #

Diberikan n titik (x_i, val_i) dengan x_i hingga 10⁹. Jawab q query: “jumlah val untuk titik dengan x di [L, R]?”. Solusi: compression + prefix sum pada indeks terkompresi.

Mekanisme #

Kompres semua x_i, L, R ke indeks [0..k-1]. Bangun array pref[] di mana pref[i] = jumlah val untuk indeks ≤ i. Query: pref[compress(R)] - pref[compress(L) - 1]. Catatan: kita perlu menemukan indeks compress untuk L yang mungkin tidak ada di array asli — gunakan lower_bound lalu sesuaikan.

Ringkasan #

Coordinate compression memetakan nilai besar ke [0..k-1] dengan k ≤ n. Pemetaan mempertahankan urutan.
Implementasi: sort + unique untuk persiapan, lower_bound untuk query. Total O(n log n).
Setelah compression, BIT/segment tree berukuran O(n) tetap layak meski nilai asli hingga 10⁹ atau 10¹⁸.
Aplikasi kanonik: count inversions (BIT + compression, O(n log n)), range query koordinat besar, offline 2D query.
Hati-hati: compression kehilangan jarak. Bila soal butuh jarak asli, pertimbangkan struktur lain.