Mảng Tiền Tố & Mảng Hiệu

1. Khái niệm & bản chất của mảng tiền tố (Prefix Sum 1D)

Mảng tiền tố (Prefix Sum) là một kỹ thuật tiền xử lý dữ liệu mảng ban đầu thành một mảng cộng dồn tích lũy, cho phép tính toán tổng của bất kỳ đoạn con liên tiếp $[L \dots R]$ nào chỉ trong $\mathcal{O}(1)$ thời gian, thay vì phải duyệt vòng lặp $\mathcal{O}(N)$.

1.1. Công thức xây dựng mảng tiền tố

Cho mảng số nguyên $A$ gồm $N$ phần tử. Quy ước đánh số chỉ số từ $1$ đến $N$ (1-based indexing):

• Khởi tạo: $P_0 = 0$.
• Công thức truy hồi với $i$ từ $1$ đến $N$: $$P_i = P_{i-1} + A_i \quad \Longleftrightarrow \quad P_i = \sum_{k=1}^{i} A_k$$

1.2. Công thức truy vấn tổng đoạn con trong $\mathcal{O}(1)$

Tổng các phần tử trong đoạn từ chỉ số $L$ đến chỉ số $R$ ($1 \le L \le R \le N$) được tính bằng hiệu của hai giá trị tiền tố: $$\text{Sum}(L, R) = \sum_{k=L}^{R} A_k = P_R - P_{L-1}$$

1.3. Chứng minh toán học

Theo định nghĩa: $$P_R = A_1 + A_2 + \dots + A_{L-1} + A_L + \dots + A_R$$ $$P_{L-1} = A_1 + A_2 + \dots + A_{L-1}$$

Lấy hiệu hai vế: $$P_R - P_{L-1} = (A_1 + \dots + A_{L-1} + A_L + \dots + A_R) - (A_1 + \dots + A_{L-1}) = A_L + A_{L+1} + \dots + A_R = \text{Sum}(L, R)$$

Bất biến toán học: Phép trừ $P_R - P_{L-1}$ đã loại bỏ chính xác đoạn tiền tố thừa từ $1$ đến $L-1$, chỉ giữ lại trọn vẹn đoạn con $[L \dots R]$ cần tính.

Ví dụ minh họa 1: Xây dựng và truy vấn Prefix Sum 1D

Cho mảng $N = 6$ phần tử: $A = [3, 1, 4, 1, 5, 9]$ (1-based indexing).

Quy tắc cộng dồn: $P[0] = 0$, $P[i] = P[i-1] + A[i]$ (ví dụ: $P[3] = 4 + 4 = 8, P[6] = 14 + 9 = 23$).

• Truy vấn 1: Tính tổng đoạn từ $L = 2$ đến $R = 5$ (đoạn $[1, 4, 1, 5]$): $$\text{Sum}(2, 5) = P[5] - P[2 - 1] = P[5] - P[1] = 14 - 3 = \mathbf{11}$$ (Kiểm tra trực tiếp: $1 + 4 + 1 + 5 = 11$ — Hoàn toàn chính xác trong $\mathcal{O}(1)$).

• Truy vấn 2: Tính tổng toàn bộ mảng từ $L = 1$ đến $R = 6$: $$\text{Sum}(1, 6) = P[6] - P[0] = 23 - 0 = \mathbf{23}$$

2. Kỹ thuật mảng tiền tố hai chiều (Prefix Sum 2D)

2.1. Bản chất nguyên lý bao hàm - Loại trừ (inclusion-exclusion principle)

Trên ma trận 2 chiều kích thước $N \times M$, gọi $P[i][j]$ là tổng của tất cả các phần tử trong hình chữ nhật có góc trái trên tại $(1, 1)$ và góc phải dưới tại $(i, j)$: $$P[i][j] = \sum_{r=1}^{i} \sum_{c=1}^{j} A[r][c]$$

2.2. Công thức xây dựng bảng tiền tố 2D trong $\mathcal{O}(N \times M)$

Tại mỗi ô $(i, j)$: $$P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + A[i][j]$$ (Giải thích: Cộng vùng phía trên và vùng bên trái, trừ đi phần giao nhau bị cộng lặp $P[i-1][j-1]$, rồi cộng thêm giá trị ô hiện tại $A[i][j]$).

2.3. Công thức truy vấn tổng hình chữ nhật $(x_1, y_1) \to (x_2, y_2)$ trong $\mathcal{O}(1)$

$$\text{Sum}((x_1, y_1), (x_2, y_2)) = P[x_2][y_2] - P[x_1-1][y_2] - P[x_2][y_1-1] + P[x_1-1][y_1-1]$$

Ví dụ minh họa 2: Truy vấn hình chữ nhật trên ma trận $3 \times 3$

Cho ma trận $A$: $$\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad \xrightarrow{\text{Xây dựng } P} \quad P = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 3 & 6 \\ 0 & 5 & 12 & 21 \\ 0 & 12 & 27 & 45 \end{bmatrix}$$

Cần tính tổng hình chữ nhật từ $(x_1=2, y_1=2)$ đến $(x_2=3, y_2=3)$ (vùng các ô $\begin{bmatrix} 5 & 6 \\ 8 & 9 \end{bmatrix}$): $$\begin{aligned} \text{Sum} &= P[3][3] - P[1][3] - P[3][1] + P[1][1] \\ &= 45 - 6 - 12 + 1 = \mathbf{28} \end{aligned}$$ (Kiểm tra trực tiếp: $5 + 6 + 8 + 9 = 28$ — Tính toán trong đúng 4 phép toán $\mathcal{O}(1)$).

3. Kỹ thuật mảng hiệu (Difference Array 1D)

3.1. Bài toán đặt ra

Cho mảng ban đầu gồm $N$ phần tử (toàn số 0 hoặc có giá trị sẵn). Thực hiện $Q$ thao tác, mỗi thao tác yêu cầu: Cộng thêm một giá trị $V$ vào tất cả các phần tử từ chỉ số $L$ đến $R$. Sau $Q$ thao tác, in ra mảng kết quả cuối cùng.

• Cách tiếp cận ngây thơ: Với mỗi thao tác, dùng vòng lặp chạy từ $L$ đến $R$ để cộng. Tổng thời gian: $\mathcal{O}(Q \times N) \approx 10^5 \times 10^5 = 10^{10}$ phép tính $\implies$ Time Limit Exceeded (TLE).
• Tối ưu bằng Mảng hiệu: Thực hiện mỗi thao tác cộng đoạn trong $\mathcal{O}(1)$ thời gian.

3.2. Cơ chế hoạt động của mảng hiệu

Xây dựng mảng hiệu $D$ thỏa mãn: $A_i = \sum_{k=1}^{i} D_k$ (Mảng ban đầu chính là mảng tiền tố của mảng hiệu). Để cộng giá trị $V$ vào mọi phần tử trong đoạn $[L \dots R]$, ta chỉ cần thực hiện 2 thao tác điểm:

• Tại điểm bắt đầu đoạn $L$: $D[L] \mathrel{+}= V$
• Tại điểm sau kết thúc đoạn $R + 1$: $D[R + 1] \mathrel{-}= V$

3.3. Khôi phục mảng kết quả sau $Q$ thao tác

Sau khi hoàn thành tất cả $Q$ thao tác cập nhật $\mathcal{O}(1)$, ta khôi phục lại mảng kết quả $A$ bằng một lần chạy tiền tố duy nhất trong $\mathcal{O}(N)$ thời gian: $$A_i = A_{i-1} + D_i \quad (i = 1 \dots N)$$

Ví dụ minh họa 3: Mảng hiệu trên dãy $N = 5$ phần tử

Ban đầu dãy toàn số 0: $A = [0, 0, 0, 0, 0]$, mảng hiệu $D = [0, 0, 0, 0, 0, 0, 0]$ (kích thước $N+2$).

1. Thao tác 1: Cộng $V = 3$ vào đoạn $[1 \dots 3] \implies D[1] += 3, D[4] -= 3$. $$D = [0, \mathbf{+3}, 0, 0, \mathbf{-3}, 0, 0]$$

2. Thao tác 2: Cộng $V = 2$ vào đoạn $[2 \dots 5] \implies D[2] += 2, D[6] -= 2$. $$D = [0, +3, \mathbf{+2}, 0, -3, 0, \mathbf{-2}]$$

Bước khôi phục mảng kết quả $A$ bằng Prefix Sum trên $D$:

• $A_1 = D_1 = 3$
• $A_2 = A_1 + D_2 = 3 + 2 = 5$
• $A_3 = A_2 + D_3 = 5 + 0 = 5$
• $A_4 = A_3 + D_4 = 5 + (-3) = 2$
• $A_5 = A_4 + D_5 = 2 + 0 = 2$

Kết quả cuối cùng: $A = [3, 5, 5, 2, 2]$

4. Kỹ thuật mảng hiệu hai chiều (Difference Array 2D)

Để cộng thêm giá trị $V$ vào tất cả các ô trong hình chữ nhật từ $(x_1, y_1)$ đến $(x_2, y_2)$ trên ma trận $N \times M$, ta chỉ cần tác động lên 4 điểm góc của mảng hiệu $2D$ trong $\mathcal{O}(1)$:

Sau khi thực hiện xong $Q$ thao tác, khôi phục ma trận gốc bằng công thức Prefix Sum 2D trong $\mathcal{O}(N \times M)$.

5. Mẫu cài đặt chuẩn thi đấu (competitive template)

Mẫu 1: Prefix Sum 1D (truy vấn tổng đoạn)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> a(n + 1);

    vector<long long> p(n + 1, 0);

    // Bước 1: Đọc dữ liệu và xây dựng mảng tiền tố O(N)
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];

        p[i] = p[i - 1] + a[i];
    }

    // Bước 2: Trả lời từng truy vấn trong O(1)
    while (q--) {
        int l, r;
        cin >> l >> r;

        cout << p[r] - p[l - 1] << "\n";
    }

    return 0;
}

Mẫu 2: Difference Array 1D (cập nhật đoạn)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    // Khởi tạo mảng hiệu kích thước n + 2 để an toàn khi truy cập r + 1
    vector<long long> d(n + 2, 0);

    // Bước 1: Tiếp nhận Q thao tác cập nhật O(1)
    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;

        d[l] += v;
        d[r + 1] -= v;
    }

    // Bước 2: Khôi phục mảng kết quả bằng tiền tố O(N)
    vector<long long> a(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + d[i];
        cout << a[i] << (i == n ? "" : " ");
    }
    cout << "\n";

    return 0;
}

6. Các bẫy lỗi lập trình thường gặp (bug traps)

1. Bẫy chỉ số 0-based vs 1-based: Khi dùng chỉ số 0-based, truy vấn đoạn bắt đầu từ $L=0$ sẽ phải tính $P[R] - P[-1]$ dẫn đến lỗi truy cập vùng nhớ ngoài biên. Khuyến nghị chuẩn: Luôn chuyển toàn bộ mảng tiền tố và mảng hiệu sang 1-based indexing với $P[0] = 0$.
2. Bẫy tràn số nguyên 32-bit khi cộng dồn: Mảng $N = 2 \cdot 10^5$ phần tử với $A_i = 10^9$ sẽ có tổng tiền tố lên tới $2 \cdot 10^{14}$, vượt ngưỡng $2 \cdot 10^9$ của int. Khai báo toàn bộ mảng $P$ và $D$ kiểu long long.
3. Bẫy tràn biên $R + 1$ trong mảng hiệu: Khi đoạn cập nhật có $R = N$, thao tác $D[R+1] -= V$ sẽ ghi vào vị trí $N + 1$. Bắt buộc phải cấp phát mảng hiệu có kích thước tối thiểu là N + 2.

7. Ranh giới áp dụng: Khi nào nên & không nên dùng?

• KHI NÀO ÁP DỤNG TỐI ƯU:
• Mảng tĩnh (Static Queries): Toàn bộ dữ liệu mảng cố định, chỉ nhận các truy vấn tính tổng đoạn liên tiếp $\implies$ Prefix Sum đạt $\mathcal{O}(1)$ tuyệt đối.

• Cập nhật Offline (Batch Updates): Nhận toàn bộ $Q$ thao tác cộng đoạn $[L, R]$ trước, sau đó mới cần in kết quả một lần ở cuối $\implies$ Difference Array đạt $\mathcal{O}(Q + N)$.

• KHI NÀO KHÔNG ÁP DỤNG ĐƯỢC (Bẫy Lỗi KỸ THUẬT):

• Cập nhật và truy vấn xen kẽ Online: Nếu chương trình vừa yêu cầu cập nhật giá trị một phần tử/đoạn, vừa yêu cầu truy vấn tổng đoạn ngay lập tức lặp đi lặp lại $Q$ lần:
• Dùng Prefix Sum sẽ tốn $\mathcal{O}(N)$ để cập nhật lại mảng $P \implies$ Tổng thời gian $\mathcal{O}(Q \times N)$ (TLE).
• Dùng Difference Array sẽ tốn $\mathcal{O}(N)$ để khôi phục mỗi khi có truy vấn $\implies$ Tổng thời gian $\mathcal{O}(Q \times N)$ (TLE).
• Giải pháp chuẩn thi đấu: Khi có cập nhật và truy vấn xen kẽ liên tục, bắt buộc phải sử dụng các cấu trúc dữ liệu cây động như Cây chỉ số nhị phân (Fenwick Tree) hoặc Cây phân đoạn (Segment Tree) (thuộc Module 08).