Wiki › Thuật toán › Nén tọa độ (Coordinate Compression)

Nén tọa độ (Coordinate Compression)

huunguyen Updated Tháng sáu 2, 2026

Nén tọa độ (coordinate compression) là kỹ thuật ánh xạ một tập giá trị có biên độ lớn (ví dụ tới $10^{9}$ hoặc $10^{18}$ ) về dải chỉ số nhỏ liên tục $[0, K)$ , trong đó $K$ là số giá trị phân biệt. Nó dựa trên một nhận xét đơn giản: rất nhiều bài toán (đếm nghịch thế, Fenwick/Segment Tree theo giá trị, sweep line) chỉ quan tâm tới thứ tự tương đối giữa các giá trị, chứ không quan tâm giá trị tuyệt đối. Khi đó ta thay giá trị thật bằng "hạng" (rank) của nó. Lợi ích: thay vì cần mảng/cây kích thước $10^{9}$ (không thể cấp phát), ta chỉ cần kích thước $K \leq N$ , biến bài toán $O (giá trị)$ bộ nhớ thành $O (N)$ , mà vẫn giữ nguyên kết quả.

Ý tưởng / Trực giác

Giả sử ta cần một cấu trúc dữ liệu đánh chỉ số theo giá trị — chẳng hạn Fenwick Tree để đếm "đã có bao nhiêu phần tử $\leq x$ ". Nếu $x$ có thể tới $10^{9}$ , ta không thể tạo mảng bit[10^9]. Nhưng với mảng $N \leq 10^{6}$ phần tử, chỉ có nhiều nhất $N$ giá trị khác nhau xuất hiện. Tất cả các giá trị còn lại không bao giờ được hỏi đến, nên chúng vô dụng.

Ý tưởng cốt lõi: chỉ những giá trị thực sự xuất hiện mới đáng được cấp một ô. Ta thu thập mọi giá trị, sắp xếp, loại trùng, rồi gán cho mỗi giá trị thật một chỉ số bằng vị trí của nó trong dãy đã sắp. Vì dãy đã sắp tăng dần, phép gán này là đơn điệu tăng:

$a_{i} < a_{j} ⟺ rank (a_{i}) < rank (a_{j}) .$

Đây là tính chất bảo toàn thứ tự — chìa khoá khiến nén tọa độ đúng. Mọi câu hỏi chỉ dựa trên so sánh (nhỏ hơn, lớn hơn, bằng, đếm số phần tử trong một khoảng theo thứ hạng) đều cho kết quả y hệt khi làm trên giá trị nén. Việc tra rank(x) được thực hiện bằng tìm kiếm nhị phân (lower_bound) trên dãy đã sắp, mất $O (\log K)$ .

Một cách nhìn khác: nén tọa độ chính là "đổi đơn vị đo trục số". Ta không quan tâm khoảng cách thật giữa hai giá trị, chỉ quan tâm ai đứng trước ai. Nếu bài toán có quan tâm khoảng cách thật (ví dụ tính diện tích, chu vi), ta vẫn nén để đánh chỉ số, nhưng khi cần độ dài đoạn thì tra ngược lại giá trị gốc qua mảng vals[].

Ví dụ chạy tay

Xét mảng giá trị lớn:

a = [ 100,  5,  100,  42,  -7 ]

Bước 1 — thu thập và sắp xếp. Copy ra sorted rồi sort:

sorted = [ -7,  5,  42,  100,  100 ]

Bước 2 — loại trùng bằng unique + erase. Hai số 100 cạnh nhau gộp lại còn một:

vals  = [ -7,  5,  42,  100 ]      (K = 4)
chỉ số:    0   1    2    3

Bước 3 — ánh xạ từng phần tử của a bằng lower_bound(vals, x) - vals.begin():

phần tử a[i]:   100    5    100    42    -7
                 ^                              <- đang xét a[0]=100
lower_bound tìm 100 trong vals -> vị trí 3

  a[0]=100  -> rank 3
  a[1]=  5  -> rank 1
  a[2]=100  -> rank 3
  a[3]= 42  -> rank 2
  a[4]= -7  -> rank 0

Kết quả mảng nén:

nén = [ 3,  1,  3,  2,  0 ]

Quan sát: trong a, ta có $- 7 < 5 < 42 < 100$ ; trong mảng nén thứ tự đó thành $0 < 1 < 2 < 3$ — thứ tự được giữ nguyên tuyệt đối, và hai giá trị bằng nhau ( $100$ ) nhận cùng một hạng ( $3$ ). Giờ mọi cấu trúc dữ liệu chỉ cần kích thước $K = 4$ .

Cài đặt

Hàm nén cơ bản, trả về mảng đã thay bằng hạng (đánh số từ 0):

// Nén tọa độ mảng a[]: trả về mảng cùng kích thước, mỗi phần tử
// được thay bằng hạng (rank) của nó trong [0, K).
vector<int> compress(vector<int> a) {
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    // loại các giá trị trùng nhau (chỉ giữ giá trị phân biệt)
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    for (int& x : a)
        // lower_bound trả về vị trí giá trị đầu tiên >= x;
        // vì x chắc chắn có trong vals nên đây đúng là hạng của x
        x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    return a; // a[i] ∈ [0, K), K = vals.size()
}

Cấu trúc tái sử dụng (gom giá trị từ nhiều nguồn rồi build một lần):

struct Compress {
    vector<int> vals;

    void add(long long x) { vals.push_back(x); } // thu thập giá trị

    void build() {                                // gọi đúng MỘT lần
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
    }

    int get(long long x) {   // giá trị thật -> hạng trong [0, K)
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    }

    long long origin(int i) { return vals[i]; } // hạng -> giá trị thật

    int size() { return (int)vals.size(); }
};

Ứng dụng kinh điển: đếm số cặp nghịch thế với giá trị tới $10^{9}$ bằng Fenwick Tree (cần nén vì không thể tạo BIT kích thước $10^{9}$ ):

long long count_inversions(vector<int> a) {
    int n = a.size();
    // --- Nén tọa độ về [1, K] (BIT đánh số từ 1) ---
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int K = vals.size();
    for (int& x : a)
        x = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;

    // --- Fenwick Tree kích thước K thay vì 10^9 ---
    vector<int> bit(K + 1, 0);
    auto update = [&](int i) { for (; i <= K; i += i & -i) bit[i]++; };
    auto query  = [&](int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; };

    long long inv = 0;
    for (int i = 0; i < n; i++) {
        // số phần tử đã thêm mà lớn hơn a[i] = i - (số <= a[i])
        inv += i - query(a[i]);
        update(a[i]);
    }
    return inv;
}

Bản Python ngắn gọn cho hàm nén:

def compress(a):
    vals = sorted(set(a))               # sắp xếp + loại trùng
    rank = {v: i for i, v in enumerate(vals)}  # giá trị -> hạng
    return [rank[x] for x in a], vals   # mảng nén và mảng tra ngược

Độ phức tạp

Gọi $N$ là số giá trị thu thập, $K \leq N$ là số giá trị phân biệt.

Thời gian dựng (build): sắp xếp $O (N \log N)$ , unique quét tuyến tính $O (N)$ . Tổng $O (N \log N)$ — chi phối bởi bước sắp xếp.
Mỗi lần tra get(x): lower_bound là tìm kiếm nhị phân trên mảng đã sắp, $O (\log K)$ . Tra ngược origin(i) chỉ là truy cập mảng, $O (1)$ .
Bộ nhớ: $O (K)$ cho mảng vals (cộng $O (N)$ tạm thời khi sắp xếp). Đây chính là điểm mấu chốt: cấu trúc dữ liệu phía sau (BIT/Segment Tree) giờ chỉ tốn $O (K)$ thay vì $O (giá trị lớn nhất)$ , giúp bài toán vừa khít bộ nhớ.

Nếu nén $M$ truy vấn rồi mỗi truy vấn tra một lần: tổng $O ((N + M) \log N)$ — vẫn rẻ hơn rất nhiều so với việc không nén (thường là bất khả thi về bộ nhớ).

⚠️ Lỗi thường gặp

Quên unique (không loại trùng). Nếu chỉ sort mà không erase(unique(...)), các giá trị bằng nhau nhận hạng khác nhau, làm sai mọi phép so sánh "bằng" và làm phình kích thước cấu trúc. Triệu chứng: đếm nghịch thế ra sai khi mảng có phần tử trùng. Luôn đi đôi sort + unique + erase.
Lẫn lộn đánh số từ 0 và từ 1. Fenwick Tree không xử lý chỉ số $0$ (vòng i += i & -i đứng yên mãi nếu $i = 0$ ). Khi nén để dùng BIT phải cộng $+ 1$ để về $[1, K]$ ; còn Segment Tree thường dùng $[0, K)$ . Chọn sai gây lệch một ô hoặc vòng lặp vô hạn.
Tràn số (overflow) khi giá trị gốc lớn. Giá trị thật có thể tới $10^{18}$ nên mảng vals và tham số get/add phải là long long, nếu để int sẽ tràn ngay khi đọc input. Lưu ý: hạng thì nhỏ (int đủ), nhưng giá trị gốc thì không.
Tra get(x) với x không có trong vals. lower_bound trả về vị trí phần tử đầu tiên $\geq x$ ; nếu $x$ chưa từng được add, ta nhận hạng của một giá trị khác. Khi cần hỏi về giá trị giữa (ví dụ "khoảng mở $(x, y)$ "), phải chủ động add các điểm biên như $x$ , $x + 1$ , $y$ , $y - 1$ vào trước khi build, nếu không tra sẽ lệch.
build() nhiều lần hoặc add sau khi đã build. Mỗi lần build phải sắp + loại trùng trên toàn bộ dữ liệu đã thu thập. Thêm giá trị mới sau khi build khiến vals không còn sắp xếp/không còn phân biệt, làm lower_bound cho kết quả rác. Quy tắc: thu thập hết -> build một lần -> chỉ get.
Nén nhầm khi cần khoảng cách thật. Trong sweep line tính diện tích/chu vi, hạng chỉ dùng để đánh chỉ số đoạn, còn độ dài mỗi đoạn phải lấy từ origin(i+1) - origin(i) (giá trị gốc), không phải hiệu của hai hạng (luôn bằng 1 — sai hoàn toàn).

Biến thể / Mở rộng

Nhiều chiều: với điểm $(x, y)$ tọa độ lớn, nén riêng từng chiều (một Compress cho trục $x$ , một cho trục $y$ ). Thường gặp trong sweep line hình học.
Nén "khoảng" thay vì "điểm": khi cần phân hoạch trục số thành các đoạn giữa các mốc liên tiếp (sweep line tính độ phủ), ta nén tập mốc rồi xét từng đoạn $[vals [i], vals [i + 1])$ với độ dài thật.
Kết hợp offline + cấu trúc dữ liệu: gom toàn bộ tọa độ trong mọi truy vấn, nén một lần, rồi chạy Fenwick/Segment Tree kích thước $K$ . Đây là khuôn mẫu của hầu hết bài "truy vấn theo giá trị lớn".

Bài tập luyện

Hàng rào kỳ lạ (Dễ) (fencebr) — (Nghiệp dư) tọa độ rào lớn nhưng thưa; nén lưới rồi BFS — bài nhập môn thấy rõ "tại sao phải nén".
Chu vi (Bạc) (perims) — (Nghiệp dư) nén các mốc tọa độ để duyệt biên hình, luyện ánh xạ giá trị về chỉ số kèm sắp xếp.
Sơn Hàng Rào (Bạc) (paintfencesi) — (Trung cấp) nén tọa độ kết hợp sweep line đếm số lớp sơn, làm quen "nén khoảng + quét".
Trồng Cỏ (Bạc) (overplants) — (Trung cấp) hình học chồng lấn: nén hai chiều rồi quét, bài chuẩn để rèn nén nhiều chiều.
Máy Phóng (slingshot) — (Chuyên gia) nén tọa độ + Segment Tree + sweep line ở mức khó, tổng hợp toàn bộ kỹ thuật.