Nén tọa độ (Coordinate Compression) ánh xạ một tập giá trị lớn (ví dụ ) về chỉ số nhỏ với là số giá trị phân biệt — cho phép dùng mảng/cây thay vì map khi chỉ quan tâm đến thứ tự tương đối, không phải giá trị tuyệt đối.
Cài đặt chuẩn
// Nén tọa độ của mảng a[]
vector<int> compress(vector<int> a) {
vector<int> sorted = a;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
// sorted[i] = giá trị thực thứ i (sau khi nén)
for (int& x : a)
x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
// Bây giờ a[i] ∈ [0, K) với K = sorted.size()
return a;
}
Cài đặt với class tái sử dụng
struct Compress {
vector<int> vals;
void add(int x) { vals.push_back(x); }
void build() {
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
}
int get(int x) { // giá trị thực → chỉ số nén [0, K)
return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}
int origin(int i) { return vals[i]; } // chỉ số nén → giá trị thực
int size() { return vals.size(); }
};
// Sử dụng:
Compress comp;
for (int x : a) comp.add(x);
comp.build();
int idx = comp.get(a[0]); // chỉ số nén của a[0]
int val = comp.origin(idx); // khôi phục giá trị thực
Ví dụ 1: Fenwick Tree với giá trị lớn
Đếm số cặp nghịch thế trong mảng với :
// Không thể dùng BIT kích thước 10^9 → nén tọa độ trước
long long count_inversions(vector<int> a) {
int n = a.size();
// Nén tọa độ
vector<int> sorted = a;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int K = sorted.size();
for (int& x : a)
x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
// Bây giờ a[i] ∈ [1, K]
// Dùng BIT kích thước K
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++) {
inv += i - query(a[i]); // số phần tử trước > a[i]
update(a[i]);
}
return inv;
}
Ví dụ 2: Segment Tree với queries offline
Các truy vấn và cập nhật có giá trị đến :
// Thu thập tất cả giá trị quan trọng trước khi xử lý
Compress comp;
for (auto& q : queries) {
comp.add(q.l);
comp.add(q.r);
}
comp.build();
// Segment tree kích thước comp.size() thay vì 10^18
SegTree seg(comp.size());
for (auto& q : queries) {
int l = comp.get(q.l), r = comp.get(q.r);
seg.update(l, r, q.val);
}
Ví dụ 3: Sweep Line
Nén tọa độ trước khi sweep theo :
// Tất cả tọa độ y của các đoạn thẳng
Compress cy;
for (auto& seg : segments) {
cy.add(seg.y1);
cy.add(seg.y2);
}
cy.build();
// Dùng segment tree kích thước cy.size() để xử lý coverage
Lưu ý quan trọng
Khi nén, thứ tự tương đối được bảo toàn:
// a[i] < a[j] ⟺ compress(a[i]) < compress(a[j])
Khi cần giá trị khoảng giữa (ví dụ: hỏi "có giá trị nào trong không"), thêm , vào tập nén:
comp.add(x); comp.add(x + 1);
comp.add(y); comp.add(y - 1);
Nhiều mảng/nhiều loại tọa độ: Nén riêng từng chiều.
Khi nào dùng nén tọa độ?
- Dùng BIT/Segment Tree nhưng giá trị lên đến –.
- Sweep line với tọa độ lớn.
- Bài toán chỉ quan tâm thứ tự tương đối, không cần giá trị tuyệt đối.
- Kết hợp với offline queries để giảm không gian.
Bình luận