Mảng cộng dồn (prefix sum) là một kĩ thuật giúp ta có thể tính nhanh các query yêu cầu tính tổng (hay một phép tính nào đó) trong một đoạn nhất định.

*Kí hiệu toán học thường dùng:* sigma: $\sum$, mang nghĩa tổng của các giá trị trong một đoạn.
VD: $\sum_{i=1}^{10} i = 1 + 2 + 3 + ... + 10$

$\sum_{i=69}^{420} i^2 = 69^2 + 70^2 + ... + 420^2$

$\sum_{i=x}^{y} ax+b = ax+b + a(x+1)+b + a(x+2)+b + ... + ay+b$

**Ví dụ:**
Cho một mảng $A$ có $N$ phần tử và $Q$ truy vấn, mỗi truy vấn gồm 2 số $l$ và $r$. Với mỗi truy vấn, in ra tổng các phần tử trong đoạn con $[l, r]$.

**Lời giải:**
Với thuật toán duyệt trâu, mỗi truy vấn ta chỉ cần lặp từ $l$, tới $r$ để tính tổng $\sum_{i=l}^r A_i$, và độ phức tạp với mỗi truy vấn sẽ là $O(N)$, và độ phức tạp của $Q$ truy vấn là $O(N \cdot Q)$:

long long GetSum(int l, int r) {
    long long s = 0;
    for(int i = l; i <= r; ++i)
        s += A[i];
    return s;
}

void Solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> A[i];
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << GetSum(l, r) << endl;
    }
}

Tuy nhiên, như vậy là không đủ nhanh cho các bài toán với $N$ và $Q$ lớn.

**Sử dụng mảng cộng dồn:**
Gọi mảng $P$ là mảng cộng dồn của $A$, ta có $P_j = \sum_{i=1}^j A_i$. Hay nói cách khác $P_j$ chính là tổng các phần tử từ $1$ tới $j$ trong mảng $A$.
Ta có thể viết lại tổng các phần tử từ $l$ tới $r$ như sau:
$$\displaylines{A_l + A_{l+1} + ... + A_{r-1} + A_r \\ = (A_1 + A_2 + ... + A_{r-1} + A_r) - (A_1 + A_2 + ... + A_{l-2} + A_{l-1}) \\ = P_r - P_{l-1}}$$
Vậy ta chỉ cần xây dựng mảng cộng dồn, sau đó với mỗi truy vấn in ra $P_r - P_{l-1}$.

**Xây dựng:**
Nhận thấy $P_i = A_1 + A_2 + ... + A_{i-1} + A_i$, $P_{i+1} = A_1 + A_2 + ... + A_{i-1} + A_i + A_{i+1} \Rightarrow P_{i+1} = P_i + A_{i+1}$

long long GetSum(int l, int r) {
    return P[r] - P[l - 1];
}

void Solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
    }
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << GetSum(l, r) << endl;
    }
}

Như vậy, độ phức tạp với mỗi truy vấn sẽ là $O(1)$, và độ phức tạp của $Q$ truy vấn là $O(Q)$.
<br>

**Mảng hiệu:**
Mảng hiệu $D$ của mảng $A$ có thể được tính bằng: $D_i = A_{i+1} - A_i$ $(1 \le i \lt n)$.

| $A$ | 1 | 7 | 3 | -2 | -1 | 5 | 0 |
| --- | - | -- | -- | -- | -- | -- | - |
| $D$ | 6 | -4 | -5 | 1 | 6 | -5 |

Để tính lại được mảng $A$ từ $D$, ta có thể dùng: $A_j = A_1 + \sum_{i=1}^{j-1} D_i$

Chứng minh: $A_1 + \sum_{i=1}^{j-1} D_i = A_1 + D_1 + D_2 + ... + D_{j-1} = A_1 + (A_2 - A_1) + (A_3 - A_2) + ... + (A_j - A_{j-1}) = A_j$

## Bài tập ví dụ:
Cho mảng $A$ gồm $N$ phần tử và số $K$, ban đầu tất cả phần tử đều bằng $0$. $K$ dòng sau đó, mỗi dòng chứa $3$ số $l$, $r$ và $v$, yêu cầu tăng các phần tử từ vị trí $l$ đến $r$ lên $v$ đơn vị. Xuất ra mảng $A$ sau khi xử lí.

**Duyệt trâu:**
Với thuật toán duyệt trâu, với mỗi $l$ $r$ ta chỉ cần duyệt qua sau đó cộng thêm $v$ vào mỗi phần tử, độ phức tạp sẽ là $O(N \cdot K)$.

**Sử dụng mảng cộng dồn và mảng hiệu:**
Ta thay đổi một chút về định nghĩa của mảng hiệu trong trường hợp này, khi này $D_i = A_i - A_{i-1}$ $(2 \le i \le N)$. Và lúc này, $A_j = A_1 + \sum_{i=2}^{j} D_i$

Để ý rằng khi tăng các phần tử trong đoạn $[l, r]$ lên $v$, giá trị $A_l - A_{l-1}$ cũng tăng lên $v$ (vì lúc này $A_l$ tăng lên $v$, trong khi $A_{l-1}$ giữ nguyên), và tương tự, giá trị $A_{r+1} - A_{r}$ giảm xuống $v$. Hay nói cách khác, $D_l$ tăng $v$ và $D_{r+1}$ giảm $v$. Vậy với mỗi $l$ $r$ $v$, ta chỉ cần thay đổi giá trị như trên, và sau cùng lấy lại mảng $A$ theo công thức ở trên.

void Solve() {
    cin >> n >> k;
    while(k--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        D[l] += v;
        D[r + 1] -= v;
    }
    for(int i = 1; i <= n; ++i) {
        D[i] += D[i - 1];
        cout << D[i] << ' ';
    }
}

<br>

Cho mảng $A$ có $N$ phần tử, tìm đoạn con có tổng các phần tử lớn nhất (có thể chọn đoạn rỗng).

**Ý tưởng:**
Với mỗi $i$ từ $1$ tới $N$, giả sử ta lấy biên phải của đoạn con là $r = i$. Vậy ta sẽ tìm một biên trái $l \le r$ sao cho $\sum_{j=l}^r A_j$ lớn nhất có thể. Dựa vào công thức $\sum_{j=l}^r A_j = P_r - P_{l-1}$, vì ta đã mặc định $r = i$ nên tổng quát lại sẽ tìm $l \le r$ sao cho $P_l$ nhỏ nhất có thể. Vậy ta có thể chạy từ đầu tới cuối, cộng dồn các giá trị, lưu lại biến $min$ và so sánh với giá trị lớn nhất.

void Solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> A[i];
    long long sum = 0, mn = 0, res = 0;
    for(int i = 1; i <= n; ++i) {
        sum += A[i];
        res = max(res, sum - mn);
        mn = min(mn, sum);
    }
    cout << res;
}

<br>

## Mảng cộng dồn 2 chiều
Cũng tương tự như 1 chiều, nhưng $P_{x, y} = \sum_{i=1}^x \sum_{j=1}^y A_{i, j}$, hay $P_{x, y} =$ tổng các giá trị trong hình chữ nhật con có góc trái trên là $(1, 1)$ và góc trái dưới là $(x, y)$.
Xét ví dụ sau đây:


Giả xử muốn tính $P_{3, 4}$, ta có thể lấy $A_{3, 4}$ (màu đỏ) $+$ $P_{3, 3}$ (màu xanh dương) $+$ $P_{2, 4}$ (màu vàng) (phần trùng màu xanh lá):


Tuy nhiên, có thể thấy rằng phần trùng màu xanh lá hay $P_{2, 3}$ sẽ được tính vào 2 lần, vì thế phải trừ bớt một lần ra $\Rightarrow P_{3, 4} = A_{3, 4} + P_{3, 3} + P_{2, 4} - P_{2, 3}$.

Vậy công thức tổng quát là $P_{i, j} = A_{i, j} + P_{i, j-1} + P_{i-1, j} - P_{i-1, j-1}$.

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

**Tính tổng của một ma trận con:**
Giả sử ta muốn tính tổng các phần tử từ $(2, 3)$ tới $(4, 4)$ (màu đỏ):


Ta có thể lấy $P_{4, 4}$ $-$ $P_{4, 2}$ (màu xanh) $-$ $P_{1, 4}$ (màu vàng) (phần trùng màu xanh lá):


Tuy nhiên, phần trùng $P_{1, 2}$ sẽ bị trừ đi 2 lần, vì thế phải cộng bù vào $\Rightarrow P_{4, 4} - P_{4, 2} - P_{1, 4} + P_{1, 2}$.

Vậy công thức tổng quát là $Sum(x_1, y_1, x_2, y_2) = P_{x_2, y_2} - P_{x_2, y_1-1} - P_{x_1-1, y_2} + P_{x_1-1, y_1-1}$

long long GetSum(int x1, int y1, int x2, int y2) {
    return P[x2][y2] - P[x2][y1 - 1] - P[x1 - 1][y2] + P[x1 - 1][y1 - 1];
}