Mảng cộng dồn (Prefix Sum) 1D & 2D: Kỹ thuật tối ưu truy vấn đoạn từ O(N) về O(1)

03/11/2026

Hãy xem xét một bài toán kinh điển luôn xuất hiện trong các đề thi tuyển sinh lớp 10 Chuyên Tin và Tin học trẻ:

Bài toán: Cho mảng gồm N = 100.000 số nguyên. Bạn nhận được Q = 100.000 câu hỏi truy vấn. Mỗi câu hỏi gồm 2 số L và R (1 \le L \le R \le N), yêu cầu tính tổng các phần tử từ vị trí L đến vị trí R:
S = a[L] + a[L+1] + ... + a[R]

Nếu bạn giải theo cách tự nhiên: mỗi truy vấn viết một vòng lặp for chạy từ L đến R để cộng dồn, thì trong trường hợp xấu nhất mỗi truy vấn tốn N phép tính. Tổng thời gian cho Q truy vấn là N \times Q = 10^5 \times 10^5 = 10^{10} phép tính → Chương trình chạy mất 100 giây và nhận 0 điểm TLE.

Kỹ thuật Mảng cộng dồn (Prefix Sum) chính là "chìa khóa vàng" giúp bạn tính toán trước toàn bộ trong O(N) và sau đó trả lời mỗi câu hỏi trong thời gian tức thì O(1)!

1. Bản chất và Công thức Prefix Sum 1 chiều

Ta tạo một mảng phụ gọi là prefix có kích thước N + 1. Trong đó prefix[i] lưu trữ tổng của tất cả các phần tử từ chỉ số 1 đến chỉ số i:

prefix[0] = 0
prefix[1] = a[1]
prefix[2] = a[1] + a[2] = prefix[1] + a[2]
prefix[3] = a[1] + a[2] + a[3] = prefix[2] + a[3]
Công thức tổng quát: prefix[i] = prefix[i - 1] + a[i]

Công thức thần thánh tính tổng đoạn [L, R]:

Tổng đoạn [L, R] = prefix[R] - prefix[L - 1]

Giải thích trực quan: prefix[R] là tổng từ 1 đến R. prefix[L - 1] là tổng từ 1 đến L - 1 (phần đứng trước L). Khi lấy prefix[R] - prefix[L - 1], ta đã loại bỏ chính xác phần thừa phía trước, chỉ giữ lại đúng đoạn từ L đến R!

2. Bảng mô phỏng thực tế

Cho mảng: a = [3, 1, 4, 1, 5, 9, 2] (chỉ số 1-indexed):

Chỉ số i	0	1	2	3	4	5	6	7
Mảng a[i]	-	3	1	4	1	5	9	2
prefix[i]	0	3	4	8	9	14	23	25

Nếu truy vấn hỏi tổng đoạn từ L = 3 đến R = 6 (đoạn [4, 1, 5, 9] có tổng là 19):

Ta chỉ cần lấy: prefix[6] - prefix[3 - 1] = prefix[6] - prefix[2] = 23 - 4 = 19! Không cần chạy bất kỳ vòng lặp nào!

3. Cài đặt C++ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu tốc độ đọc ghi
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    if (!(cin >> n >> q)) return 0;
    
    // Sử dụng long long để tránh tràn số khi cộng dồn
    vector<long long> a(n + 1);
    vector<long long> prefix(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i]; // Xây dựng prefix sum trong O(N)
    }
    
    // Trả lời mỗi truy vấn trong O(1):
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << "\n";
    }
    
    return 0;
}

4. Prefix Sum 2D — Tổng miền hình chữ nhật trên ma trận

Cho ma trận kích thước N \times M. Bạn cần tính tổng các số trong miền hình chữ nhật có góc trên-trái tại (r1, c1) và góc dưới-phải tại (r2, c2) trong thời gian O(1).

Công thức xây dựng bảng cộng dồn 2 chiều:

pref[i][j] = a[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];

Công thức truy vấn tổng hình chữ nhật (r1, c1) → (r2, c2):

long long total = pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1];

(Nguyên lý Bao hàm - Loại trừ: khi trừ phần trên và phần trái, góc giao pref[r1-1][c1-1] bị trừ 2 lần nên phải cộng bù lại một lần).

5. Mảng hiệu (Difference Array) — Cập nhật đoạn trong O(1)

Nếu Prefix Sum là bài toán: "Mảng tĩnh, tính tổng đoạn liên tục", thì Mảng hiệu (Difference Array) giải quyết bài toán ngược lại:

Có Q thao tác: mỗi thao tác yêu cầu cộng thêm giá trị V vào tất cả các phần tử từ chỉ số L đến chỉ số R. Hãy in ra mảng kết quả sau Q lần cập nhật.

Thay vì duyệt cộng mất O(N \times Q), ta dùng mảng hiệu diff:

// Cộng V vào đoạn [L, R] chỉ tốn 2 thao tác O(1):
diff[L] += V;
diff[R + 1] -= V;

// Sau khi thực hiện xong tất cả Q truy vấn, khôi phục lại mảng gốc bằng Prefix Sum:
for (int i = 1; i <= n; i++) {
    diff[i] += diff[i - 1];
    a[i] += diff[i];
}

#C++#Thuật toán #Mảng cộng dồn