Cấu trúc dữ liệu và Giải thuật Bài 17: Mảng hiệu (Difference Array): Cập nhật khoảng dữ liệu nhanh chóng.

Ở Bài 16, chúng ta đã dùng Prefix Sum để giải quyết bài toán "Truy vấn nhanh một khoảng". Nhưng hãy đặt vào một kịch bản hệ thống khác: Bạn đang xây dựng hệ thống đặt vé xe lửa cho một tuyến đường có 1000 ga. Mỗi ngày có hàng chục ngàn hành khách đặt vé. Một khách hàng báo: "Tôi muốn mua 3 vé đi từ ga số 200 đến ga số 500".

Nhiệm vụ của server là phải cộng thêm 3 hành khách vào sức chứa của tất cả các ga từ 200 đến 500 để kiểm tra xem tàu có bị quá tải không. Nếu dùng vòng lặp chạy từ ga 200 đến 500 để cộng từng ga một ($O(N)$), với hàng chục ngàn request liên tục ($Q$), server sẽ sụp đổ vì độ phức tạp $O(Q \times N)$.

Lúc này, chúng ta cần một phép màu toán học ngược lại với Prefix Sum: Mảng hiệu (Difference Array) — cho phép cập nhật hàng vạn phần tử chỉ với $O(1)$.

1. Bản chất của Mảng hiệu

Nếu Mảng cộng dồn lưu "tổng của các phần tử phía trước", thì Mảng hiệu lưu "sự chênh lệch giữa phần tử hiện tại và phần tử ngay trước nó".

Cho một mảng gốc A = [A[0], A[1], A[2], ..., A[N-1]].

Mảng hiệu D được xây dựng bằng công thức:

• D[0] = A[0]

• D[i] = A[i] - A[i-1] (với $i > 0$)

Ví dụ, mảng gốc biểu diễn số khách trên tàu: A = [2, 5, 8, 8, 3]

Mảng hiệu sẽ là:

• D[0] = 2

• D[1] = 5 - 2 = 3

• D[2] = 8 - 5 = 3

• D[3] = 8 - 8 = 0

• D[4] = 3 - 8 = -5

  Kết quả: D = [2, 3, 3, 0, -5].

2. Phép màu O(1): Cập nhật cả một khoảng dữ liệu

Quay lại bài toán đặt vé: Giả sử ban đầu tàu trống trơn, mảng A toàn số 0. Suy ra mảng D cũng toàn số 0.

Hành khách mua 10 vé từ ga số L = 1 đến ga số R = 3. Tức là bạn cần cộng thêm 10 vào các vị trí A[1], A[2], A[3].

Thay vì dùng vòng lặp, bạn chỉ cần thao tác đúng 2 phép tính trên mảng hiệu D:

1. D[L] += 10: Đánh dấu tại vị trí bắt đầu L, giá trị đã tăng vọt lên thêm 10 so với trước đó.

2. D[R + 1] -= 10: Đánh dấu tại vị trí R + 1 (ngay sau khi hành khách xuống tàu), giá trị sụt giảm đi 10 so với nhà ga trước đó.

Với ví dụ trên:

• D[1] += 10 $\rightarrow$ D = [0, 10, 0, 0, 0, 0]

• D[4] -= 10 $\rightarrow$ D = [0, 10, 0, 0, -10, 0]

Chỉ mất đúng 2 dòng code, thời gian thực thi là $O(1)$. Dù khoảng cách từ L đến R là 3 ga hay 3 triệu ga, server vẫn chỉ làm 2 phép tính này. Nếu có 100,000 khách đặt vé, bạn thao tác 100,000 lần $O(1)$, tổng thời gian chỉ là $O(Q)$ cực kỳ nhẹ nhàng.

3. Khôi phục mảng gốc (Prefix Sum của Difference Array)

Sau khi xử lý xong hàng vạn request cộng/trừ $O(1)$ vào mảng D, làm sao để biết được thực tế tại ga số 2 đang có bao nhiêu người?

Đây là lúc tính chất toán học tuyệt đẹp xuất hiện: Mảng cộng dồn (Prefix Sum) của Mảng hiệu (Difference Array) chính là Mảng gốc ban đầu.

Thử tính mảng cộng dồn của D = [0, 10, 0, 0, -10, 0] vừa tạo ở trên:

• A[0] = D[0] = 0

• A[1] = A[0] + D[1] = 0 + 10 = 10

• A[2] = A[1] + D[2] = 10 + 0 = 10

• A[3] = A[2] + D[3] = 10 + 0 = 10

• A[4] = A[3] + D[4] = 10 + (-10) = 0

• A[5] = A[4] + D[5] = 0 + 0 = 0

Kết quả khôi phục: A = [0, 10, 10, 10, 0, 0]. Chú ý thấy chính xác các vị trí từ 1 đến 3 đều đã được cộng thêm 10! Thao tác khôi phục này tốn $O(N)$ và chỉ cần chạy một lần duy nhất vào cuối ngày, hoặc khi thực sự cần đọc dữ liệu tổng hợp.

4. Triển khai bằng Golang

Dưới đây là một template hàm xử lý kinh điển cho mọi bài toán dạng "Cập nhật hàng loạt (Batch Updates)":

Go

// Truyền vào kích thước mảng n và danh sách các lệnh cập nhật dạng [L, R, Value]
func getFinalArray(n int, updates [][]int) []int {
    // Khai báo mảng hiệu kích thước n + 1 để không bị lỗi tràn viền (Out of Bounds) khi trừ D[R+1]
    diff := make([]int, n+1) 
    
    // Xử lý tất cả các lệnh cập nhật trong O(Q)
    for _, update := range updates {
        L := update[0]
        R := update[1]
        V := update[2]
        
        diff[L] += V
        if R+1 < n {
            diff[R+1] -= V
        }
    }
    
    // Khôi phục mảng gốc trong O(N)
    result := make([]int, n)
    result[0] = diff[0]
    for i := 1; i < n; i++ {
        result[i] = result[i-1] + diff[i]
    }
    
    return result
}

5. Mảng cộng dồn vs. Mảng hiệu: Cặp bài trùng

Để dễ nhớ khi nào nên dùng cấu trúc nào trong phòng phỏng vấn hệ thống (System Design) hoặc lúc viết thuật toán:

• Prefix Sum (Mảng cộng dồn): Khi dữ liệu đứng yên (không cập nhật), nhưng có hàng vạn yêu cầu Đọc/Truy vấn tính tổng một khoảng $\rightarrow$ Đọc $O(1)$, Cập nhật $O(N)$.

• Difference Array (Mảng hiệu): Khi người dùng không có nhu cầu xem ngay, nhưng có hàng vạn yêu cầu Ghi/Cập nhật vào một khoảng liên tục $\rightarrow$ Cập nhật $O(1)$, Đọc $O(N)$ (do phải khôi phục).

Hai cấu trúc này bù trừ hoàn hảo cho nhau và là nền tảng không thể thiếu khi làm việc với dữ liệu chuỗi thời gian (Time-series data) hoặc lịch trình (Scheduling).

Khi xử lý dữ liệu, đôi khi chúng ta không quan tâm đến "tổng" hay "hiệu", mà quan tâm đến việc một phần tử đã xuất hiện bao nhiêu lần trong không gian RAM cực kỳ chật hẹp. Đó là bài toán đếm tần số.