Hôm nay ngoài hai kỹ thuật kinh điển là mảng tiền tố và mảng hiệu, chúng ta còn làm quen với một công cụ thiết yếu khi xử lý dữ liệu thưa: rời rạc hóa.

Mảng tiền tố (Prefix Sum)

Mảng tiền tố chủ yếu giải quyết các bài toán truy vấn đoạn không cập nhật, đặc biệt khi hàm truy vấn có tính chất khả trừ: giá trị trên đoạn [l, r] có thể suy ra từ giá trị trên [1, r] và [1, l−1]. Với mảng một chiều a[1..n], mảng tiền tố s được định nghĩa:
s[i] = a[1] + a[2] + ... + a[i] Ta xây dựng s trong O(n) bằng công thức đệ quy:

for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + a[i];
}

Khi đó, tổng trên đoạn [l, r] là:
s[r] − s[l − 1] Tuy nhiên, mảng tiền tố không hỗ trợ thao tác sửa đổi phần tử — nếu cần cả truy vấn lẫn cập nhật, cấu trúc như cây Fenwick hoặc segment tree sẽ phù hợp hơn.

Mảng tiền tố hai chiều

Với ma trận a[1..n][1..m], mảng tiền tố hai chiều s được định nghĩa:
s[i][j] = tổng tất cả a[x][y] với 1 ≤ x ≤ i, 1 ≤ y ≤ j Công thức xây dựng:

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    }
}

Tổng trên hình chữ nhật từ (x₁, y₁) đến (x₂, y₂) (tọa độ bắt đầu từ 1):
s[x₂][y₂] − s[x₁−1][y₂] − s[x₂][y₁−1] + s[x₁−1][y₁−1]

Mảng hiệu (Difference Array)

Mảng hiệu là phép biến đổi nghịch đảo của mảng tiền tố. Với mảng a, mảng hiệu d thỏa mãn:
a[i] = d[1] + d[2] + ... + d[i] Do đó, ta dễ dàng suy ra:
d[1] = a[1], và với i > 1: d[i] = a[i] − a[i−1] Cách xây dựng:

for (int i = 1; i <= n; ++i) {
    d[i] = a[i] - a[i - 1];
}

Ứng dụng nổi bật nhất của mảng hiệu là thực hiện nhiều thao tác cộng đoạn trong O(1) mỗi lần, sau đó khôi phục mảng gốc bằng một lần duyệt O(n): - Để cộng k vào toàn bộ đoạn [l, r]: d[l] += k; d[r + 1] -= k; (giả sử d có kích thước đủ lớn để tránh tràn) Sau khi áp dụng tất cả các thao tác, chạy lại mảng tiền tố trên d sẽ thu được mảng a đã được cập nhật.

Rời rạc hóa (Coordinate Compression)

Khi các giá trị đầu vào có miền giá trị rất lớn (ví dụ lên tới 10⁹) nhưng số lượng phần tử lại nhỏ (ví dụ chỉ vài chục nghìn), ta dùng rời rạc hóa để ánh xạ chúng vào một dãy số nguyên liên tục bắt đầu từ 1. Quy trình tiêu biểu:

1. Thu thập tất cả giá trị cần rời rạc (các điểm mút đoạn, tọa độ, v.v.)
2. Sắp xếp và loại bỏ trùng lặp
3. Gán nhãn thứ tự tăng dần cho từng giá trị duy nhất

Ví dụ cài đặt bằng std::vector và std::sort:

vector<long long> coords;
// thêm tất cả giá trị cần rời rạc vào coords
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());

// Hàm chuyển giá trị gốc → chỉ số rời rạc
auto get_id = [&](long long x) {
    return lower_bound(coords.begin(), coords.end(), x) - coords.begin() + 1;
};

Nếu cần ánh xạ ngược (chỉ số → giá trị gốc), lưu vào mảng riêng hoặc vector phụ.

Bài tập minh họa

Bài D – Dãy con "tốt"

Yêu cầu đếm số đoạn con có tổng bằng độ dài đoạn. Chuyển đổi: đặt b[i] = a[i] − 1, khi đó bài toán trở thành đếm số đoạn con có tổng bằng 0 trên mảng b. Dùng mảng tiền tố p và đếm tần suất các giá trị p[i] bằng unordered_map.

Bài G – Bầu trời sao

Mỗi ngôi sao tại (x, y) có độ sáng thay đổi tuần hoàn theo thời gian với chu kỳ c+1. Giải pháp: tiền xử lý c+1 ma trận tĩnh — mỗi ma trận ứng với một pha độ sáng tại thời điểm t mod (c+1), rồi xây dựng mảng tiền tố hai chiều cho từng ma trận.

Bài H – Số điểm được bao phủ

Cho n đoạn trên trục số, đếm số điểm bị bao phủ đúng k lần (với k = 1, 2, ..., n). Thực hiện rời rạc hóa tất cả điểm mút và các vị trí lân cận (l−1, r+1), sau đó dùng mảng hiệu một chiều để đánh dấu các đoạn, rồi quét tuyến tính để tính số điểm trên từng khoảng rời rạc.

Bài I – Bản đồ mới của Valiant

Tìm cạnh lớn nhất l sao cho tồn tại hình vuông l × l mà mọi ô trong nó đều có giá trị ≥ l. Áp dụng tìm kiếm nhị phân trên l, với hàm kiểm tra dùng mảng tiền tố hai chiều để xác minh nhanh tính chất "toàn bộ ≥ l" trên mọi hình vuông kích thước l.

Bài J – Trừ cực hạn

Cho phép trừ một hằng số từ bất kỳ tiền tố hoặc hậu tố nào. Kiểm tra xem có thể đưa toàn bộ mảng về 0 hay không. Chuyển sang mảng hiệu d. Mỗi phép trừ tiền tố [1, k] tương đương với d[1]−=x, d[k+1]+=x; mỗi phép trừ hậu tố [k, n] tương đương với d[k]−=x. Từ đó suy ra điều kiện khả thi dựa trên tổng tuyệt đối các phần tử âm trong d[2..n] và giới hạn từ d[1].

Bài K – Những viên đá phép

Một phép biến đổi thay c[i] bằng c[i−1] + c[i+1] − c[i]. Phân tích trên mảng hiệu d[i] = c[i+1] − c[i] cho thấy phép biến đổi tương đương với hoán vị hai phần tử liền kề trong d. Do đó, hai dãy ban đầu và đích có thể biến đổi qua nhau khi và chỉ khi:

• c1[1] == c2[1] và c1[n] == c2[n]
• Hai mảng hiệu (có độ dài n−1) là hoán vị của nhau (sau khi sắp xếp)