CTDL & giải thuật

Nén tọa độ: biến giá trị lớn thành chỉ số

Giá trị có thể tới một tỷ nhưng chỉ vài trăm nghìn giá trị thực sự xuất hiện. Nén tọa độ thay giá trị bằng thứ hạng để cấu trúc dữ liệu dùng mảng gọn.

Thu nhỏ miền giá trị, không làm mất thứ tự

Một mảng chỉ có 100.000 phần tử nhưng giá trị tới 10^9 không thể dùng giá trị làm chỉ số trực tiếp. Nén tọa độ thay mỗi giá trị bằng hạng trong danh sách các giá trị phân biệt đã sắp. Miền mới có kích thước tối đa n và thích hợp cho Fenwick, Segment Tree hoặc mảng tần suất.

Ý chính

Nén giữ quan hệ bằng nhau và thứ tự: x < y khi và chỉ khi rank(x) < rank(y), và x = y khi và chỉ khi rank(x) = rank(y). Nó không giữ khoảng cách số học; chênh lệch hai hạng không phải chênh lệch hai giá trị.

Nén tọa độ: a = [100, -5, 100, 7] → rank = [2, 0, 2, 1] a[0] = 100 a[1] = -5 a[2] = 100 a[3] = 7 Mảng duy nhất đã sắp: u = [-5 (0), 7 (1), 100 (2)] rank = 2 rank = 0 rank = 2 rank = 1
Nén tọa độ: [100, -5, 100, 7] 1. Mảng gốc có số âm & trùng a = [100, -5, 100, 7] 2. Sắp tăng và xóa trùng u = [-5, 7, 100] (mốc 0, 1, 2) 3. Tra vị trí lower_bound rank = [2, 0, 2, 1] Giữ nguyên thứ tự · O(n log n)
Hình 1. Sắp xếp, khử trùng và ánh xạ mảng [100, -5, 100, 7] về hạng 0..2.

Ba bước của bản tĩnh

Sao chép mảng sang unique_values, sắp tăng, rồi xóa phần tử trùng kề nhau. Với mỗi x trong mảng gốc, hạng 0-based là vị trí lower_bound(unique_values,x). Python có thể dựng dictionary {value:rank} sau khi sắp để ánh xạ tuyến tính.

Ví dụ 100,-5,100,7 tạo danh sách -5,7,100. Hạng lần lượt là 2,0,2,1. Hai số 100 nhận cùng hạng; -5 nhỏ hơn 7 nên 0 nhỏ hơn 1. Nhưng khoảng cách từ -5 tới 7 là 12, còn khoảng cách hạng chỉ 1.

Mảng rỗng cho danh sách và dãy hạng rỗng. Một giá trị lặp nhiều lần cho đúng một tọa độ. Hai ca này bắt lỗi code giả định unique_values[0] luôn tồn tại hoặc tăng hạng cho từng vị trí thay vì từng giá trị khác nhau.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;using ll=long long;
int main(){int n=4;vector<ll>a={100,-5,100,7};if(cin>>n){a.resize(n);for(auto&x:a)cin>>x;}vector<ll>u=a;sort(u.begin(),u.end());u.erase(unique(u.begin(),u.end()),u.end());cout<<u.size()<<'\n';for(ll x:u)cout<<x<<' ';cout<<'\n';for(ll x:a)cout<<lower_bound(u.begin(),u.end(),x)-u.begin()<<' ';cout<<'\n';}

Sắp xếp tốn O(n log n), xóa trùng O(n). C++ tìm nhị phân từng phần tử nên thêm O(n log n); Python dựng map rồi ánh xạ trung bình O(n). Bộ nhớ O(n). Nếu dữ liệu đã sắp hoặc miền nhỏ, có thể có cách đơn giản hơn.

Dùng hạng với Fenwick

Fenwick thường đánh chỉ số 1-based, trong khi rank mẫu là 0-based. Khi cập nhật, dùng rank+1. Đếm số phần tử nhỏ hơn x bằng prefix tới rank(x), không gồm chính hạng x. Đếm nhỏ hơn hoặc bằng dùng prefix tới rank+1. Một dấu cộng sai sẽ lộ rõ khi có phần tử trùng.

Đếm nghịch thế: duyệt từ phải sang trái, đáp án tăng bằng số phần tử đã thấy có hạng nhỏ hơn hiện tại; sau đó thêm hạng hiện tại vào Fenwick. Nén cần thiết vì giá trị âm/lớn, còn Fenwick chỉ quan tâm thứ tự.

Segment Tree cũng dùng hạng làm lá. Bài tìm phần tử thứ k có thể lưu tần suất theo hạng, đi xuống cây rồi đổi hạng trở lại unique_values[rank]. Luôn giữ mảng giải nén nếu đầu ra cần giá trị gốc.

Hình học cần độ dài thật

Trong Sweep Line, nén các mốc y giúp tạo các khoảng giữa mốc. Tuy nhiên độ dài lá i là ys[i+1]-ys[i], không phải 1. Nếu các mốc là 0, 100 và 101, hai khoảng có độ dài 100 và 1 dù hạng đều cách nhau một.

Tương tự, không thể tính khoảng cách Manhattan hoặc Euclid bằng hạng. Nén chỉ thích hợp cho phép so thứ tự, bằng nhau, đếm và cấu trúc đánh chỉ số. Khi công thức dùng hiệu giá trị, tra lại tọa độ gốc.

Cẩn thận

Đừng áp dụng phép % n để “nén” số lớn. Hai giá trị khác nhau có thể trùng phần dư và thứ tự bị phá; đó không phải coordinate compression.

Dữ liệu trực tuyến và ngoại tuyến

Bản tĩnh cần biết trước mọi giá trị sẽ xuất hiện. Nếu có cập nhật gán giá trị mới trong danh sách truy vấn, hãy đưa cả giá trị ban đầu lẫn mọi giá trị cập nhật vào danh sách nén trước khi xử lý. Bỏ sót một giá trị khiến lower_bound trả vị trí chèn không có lá tương ứng.

Nếu giá trị đến thật sự trực tuyến và không thể biết trước, nén tĩnh không đủ. Có thể dùng cây cân bằng có order statistics, dynamic segment tree trên miền lớn, hoặc thu thập theo lô rồi xây lại. Dictionary gán hạng theo thứ tự đến giữ bằng nhau nhưng không giữ thứ tự giá trị, nên không thay được nén đã sắp.

Các lỗi triển khai

Không xóa trùng tạo nhiều hạng cho cùng giá trị tùy cách tìm. Gán hạng theo vị trí trong mảng đã sắp nhưng quên xử lý trùng cũng gây lỗi đó. Trộn rank 0-based với cấu trúc 1-based dẫn vòng lặp Fenwick kẹt ở chỉ số 0. Giải nén bằng mảng gốc thay vì unique_values trả sai giá trị.

Một lỗi tinh tế là nén riêng từng đầu của truy vấn rồi so hạng giữa hai bảng khác nhau. Các giá trị cần so với nhau phải nằm trong cùng một hệ tọa độ nén.

Tự kiểm tra hàm nén mà không dùng lower_bound

Để kiểm tra mảng hạng và bảng giải nén mà không phụ thuộc vào lower_bound hay dict, bạn có thể tính hạng của từng phần tử x trên mảng nhỏ bằng định nghĩa trực tiếp: đếm xem trong tập các giá trị phân biệt của mảng có bao nhiêu giá trị nhỏ hơn x nghiêm ngặt. Hãy thử các trường hợp có số âm, nhiều phần tử trùng nhau, giá trị biên 10^9 / -10^9 và mảng rỗng.

Ngoài việc so từng phần tử, bạn có thể viết một vòng lặp kiểm tra trực tiếp tính chất bảo toàn thứ tự cho mọi cặp chỉ số (i, j): a[i] < a[j] khi và chỉ khi rank[i] < rank[j], và a[i] == a[j] khi và chỉ khi rank[i] == rank[j]. Thêm hai điều kiện unique_values[rank[i]] == a[i] và các hạng phủ kín 0..k-1 không có khoảng trống, bạn xác nhận được phép nén và giải nén đúng trên mảng đang thử; chạy trên nhiều mảng ngẫu nhiên nhỏ để tăng độ tin cậy.

Kiểm ba thuộc tính của phép nén

Không cần biết trước toàn bộ dãy hạng để tự kiểm. Với mọi cặp vị trí i,j: giá trị bằng nhau phải có hạng bằng nhau; giá trị nhỏ hơn phải có hạng nhỏ hơn; mọi hạng phải nằm trong 0..k-1 và không có khoảng trống.

Đầu vào Danh sách duy nhất Hạng
100,-5,100,7 -5,7,100 2,0,2,1
9,9,9 9 0,0,0
rỗng rỗng rỗng
10^9,-10^9 -10^9,10^9 1,0

Sau khi kết hợp Fenwick, kiểm riêng phép đổi từ hạng 0-based sang chỉ số 1-based. Một cập nhật tại chỉ số 0 làm vòng lặp Fenwick không tiến; vì thế phép cộng 1 nên nằm ở biên gọi cấu trúc, không rải rác trong công thức.

Nén khi có truy vấn cập nhật

Nếu biết trước toàn bộ thao tác, hãy thu thập giá trị ban đầu cùng mọi giá trị sẽ được gán hoặc hỏi, rồi nén một lần. Sau đó xử lý truy vấn theo thứ tự gốc. Chỉ nén mảng ban đầu sẽ khiến giá trị mới không có hạng, còn tự chèn vào giữa làm thay đổi hạng cũ và phá dữ liệu Fenwick.

Trong bài sweep line, đôi khi cần thêm cả y1 và y2; trong bài dùng khoảng giữa, lá đại diện cặp mốc kề nhau nên số lá là k-1. Trong bài hỏi số giá trị nhỏ hơn x mà x không xuất hiện, lower_bound vẫn trả số mốc nhỏ hơn và không cần chèn x, miễn cấu trúc chỉ lưu dữ liệu đã biết.

Nén nhiều chiều thường làm riêng từng trục nếu các phép so x và y độc lập. Không ghép (x,y) thành một hạng duy nhất rồi kỳ vọng giữ được thứ tự trên từng trục. Hãy ghi rõ quan hệ cần bảo toàn—bằng nhau, thứ tự toàn phần hay khoảng cách—trước khi chọn cách ánh xạ.

Kiểm tra ánh xạ hai chiều

Sau khi tạo mảng mốc đã sắp và bỏ trùng, thử khôi phục vài giá trị bằng value[rank[x]]. Nếu kết quả không đúng x, ánh xạ đã sai. Với chỉ số một gốc cho Fenwick, nên cộng một đúng tại lớp giao tiếp rồi giữ toàn bộ cấu trúc bên trong nhất quán; cộng trừ rải rác ở nhiều nơi là nguồn lỗi lệch chỉ số phổ biến.

Luyện ngay trên Big-O Coding

Hai bài dưới đây luyện nén tọa độ: một bài nén trực tiếp và một bài dùng nén để chuẩn bị cho cây Fenwick.

Bài đầu thực hành nén trực tiếp. Bài nghịch thế cho thấy lý do nén kết hợp Fenwick, không chỉ yêu cầu in hạng.

Câu hỏi thường gặp

Hạng nên bắt đầu từ 0 hay 1?

Cả hai được. Dùng 0 trong mảng thông thường; cộng 1 tại biên khi gọi Fenwick.

Nén có làm thay đổi đáp án so sánh không?

Không với <, >, ==. Nó làm mất khoảng cách, nên không thay giá trị trong công thức số học.

Có cần lưu map không?

Không bắt buộc. C++ có thể lower_bound mỗi lần; map giúp ánh xạ nhanh hơn khi lặp nhiều.

Muốn học bài bản cùng giảng viên?

Luyện phỏng vấn Google, Meta, Amazon theo Interview Patterns: 16 buổi online live, lớp 7–15 người, C++/Python/Java. Học thử buổi 1 miễn phí.

Xem Khóa Blue 2.0

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483