Cấu trúc dữ liệu và Giải thuật Bài 16: Mảng cộng dồn (Prefix Sum): Tính tổng đoạn con trong O(1).

Khi xây dựng các API thống kê cho hệ thống e-commerce, một trong những truy vấn phổ biến nhất mà backend phải xử lý là tính toán tổng doanh thu hoặc lưu lượng truy cập trong một khoảng thời gian cụ thể (từ ngày L đến ngày R).

Nếu database đã trả về một mảng chứa doanh thu của 365 ngày trong năm, làm thế nào để bạn trả lời hàng ngàn request yêu cầu tính tổng của các khoảng ngày khác nhau mà không làm sập CPU của server? Giải pháp chính là kỹ thuật Mảng cộng dồn (Prefix Sum).

1. Nút thắt cổ chai của cách tính thông thường (Brute Force)

Giả sử bạn có mảng A chứa doanh thu của 7 ngày: A = [10, 20, 10, 50, 20, 30, 40]

Khi có yêu cầu tính tổng doanh thu từ ngày 2 đến ngày 5 (index L = 2, R = 5), phản xạ tự nhiên là dùng một vòng lặp chạy từ L đến R và cộng dồn các giá trị lại: 10 + 50 + 20 + 30 = 110.

• Thời gian cho 1 truy vấn: O(K) với K là độ dài đoạn cần tính. Trong trường hợp xấu nhất (tính từ đầu đến cuối mảng), nó là O(N).

• Thời gian cho Q truy vấn: Nếu dashboard của bạn có 100,000 người dùng cùng lúc kéo thanh trượt để xem báo cáo (Q = 100,000), tổng số phép tính sẽ là O(Q × N). Hệ thống sẽ ngay lập tức rơi vào trạng thái nghẽn cổ chai.

2. Kỹ thuật Prefix Sum: Làm một lần, dùng mãi mãi

Tư duy cốt lõi của Prefix Sum là tính toán trước (Pre-computation). Thay vì để đến lúc người dùng hỏi mới bắt đầu cộng, chúng ta tính sẵn tổng từ đầu mảng đến mọi vị trí và lưu vào một mảng mới gọi là mảng P (Prefix array).

Công thức khởi tạo:

• P[0] = A[0]

• P[i] = P[i-1] + A[i] (với i > 0)

Áp dụng vào mảng A = [10, 20, 10, 50, 20, 30, 40], ta xây dựng được mảng P:

• P[0] = 10

• P[1] = 10 + 20 = 30

• P[2] = 30 + 10 = 40

• P[3] = 40 + 50 = 90

• P[4] = 90 + 20 = 110

• P[5] = 110 + 30 = 140

• P[6] = 140 + 40 = 180

Mảng cộng dồn hoàn chỉnh: P = [10, 30, 40, 90, 110, 140, 180]. Thao tác này chỉ cần chạy đúng 1 vòng lặp, tốn O(N) thời gian và O(N) không gian bộ nhớ.

3. Phép màu O(1): Công thức truy vấn thần tốc

Bây giờ, nếu muốn tính tổng từ L = 2 đến R = 5, bạn không cần vòng lặp nào cả. Hãy nhìn vào mảng P:

• P[5] là tổng từ đầu đến ngày 5 (từ index 0 đến 5).

• P[1] là tổng từ đầu đến ngày 1 (từ index 0 đến 1) — tức là phần chúng ta không muốn tính.

Vậy, tổng từ L đến R chính là phần còn lại sau khi lấy P[R] trừ đi phần không lấy P[L-1].

Công thức truy vấn: Sum(L, R) = P[R] - P[L-1] (nếu L > 0) Trường hợp L = 0, kết quả chính là P[R].

Áp dụng công thức: Sum(2, 5) = P[5] - P[1] = 140 - 30 = 110. Kết quả chuẩn xác và chỉ tốn đúng 1 phép trừ, tức là thời gian O(1).

Dù có 1 triệu request (Q = 1,000,000), hệ thống vẫn xử lý nhẹ nhàng trong O(Q) thay vì O(Q × N).

4. Triển khai cấu trúc Prefix Sum bằng Golang

Khi thiết kế backend bằng Golang, logic của Prefix Sum thường được đóng gói thành một struct để dễ dàng tái sử dụng trong các service thống kê:

Go

type PrefixSum struct {
	prefix []int
}

// Khởi tạo mảng cộng dồn tốn O(N)
func NewPrefixSum(arr []int) *PrefixSum {
	n := len(arr)
	if n == 0 {
		return &PrefixSum{prefix: []int{}}
	}

	p := make([]int, n)
	p[0] = arr[0]
	for i := 1; i < n; i++ {
		p[i] = p[i-1] + arr[i]
	}
	return &PrefixSum{prefix: p}
}

// Truy vấn tốn O(1)
func (ps *PrefixSum) Query(L, R int) int {
	if L < 0 || R >= len(ps.prefix) || L > R {
		return 0 // Bắt lỗi ranh giới (Edge cases)
	}
	if L == 0 {
		return ps.prefix[R]
	}
	return ps.prefix[R] - ps.prefix[L-1]
}

5. Điểm giới hạn (Trade-off) của Prefix Sum

Prefix Sum là vũ khí tối thượng cho dữ liệu tĩnh (Static Data) — tức là khi dữ liệu trong mảng không bị thay đổi sau khi đã khởi tạo mảng P.

Tuy nhiên, nếu người dùng liên tục cập nhật dữ liệu (ví dụ: sửa lại doanh thu của ngày số 2), mảng P sẽ bị sai lệch. Để mảng P đúng trở lại, bạn phải tính toán lại toàn bộ các phần tử từ index 2 đến cuối mảng, tốn O(N) thời gian. Nếu hệ thống có số lượng lệnh cập nhật (Update) ngang ngửa với lệnh truy vấn (Query), ưu thế O(1) của Prefix Sum sẽ bị vô hiệu hóa hoàn toàn bởi chi phí O(N) của mỗi lần Update.

Để giải quyết bài toán vừa truy vấn nhanh vừa cập nhật nhanh, hệ thống sẽ cần đến các cấu trúc dữ liệu thiết kế cho hệ thống phân tán mạnh mẽ hơn như Segment Tree hoặc Fenwick Tree (sẽ được đề cập ở Chương 20).

Kỹ thuật Mảng cộng dồn dùng để truy xuất dữ liệu rất nhanh. Nhưng nếu bạn cần thực hiện yêu cầu ngược lại: Cập nhật liên tục một khoảng dữ liệu dài (ví dụ: cộng thêm 50 điểm kinh nghiệm cho tất cả người chơi từ cấp 10 đến 50) trong thời gian O(1), chúng ta sẽ cần đến một kỹ thuật "chị em" của Prefix Sum ở bài học tiếp theo.