Tác giả:
- Bùi Nguyễn Đức Tân - VNU-HCM, High School for the Gifted
Reviewer:
- Trần Quang Lộc - ITMO University
- Hoàng Xuân Nhật - VNU-HCM, University of Science
- Nguyễn Phú Bình - Hung Vuong High School for the Gifted, Binh Duong Province
[[TOC]]
Cho một mảng
-
$S_0 = c$ , với$c$ là một hằng số thực -
$S_i = S_{i - 1} + A_{i -1} = \displaystyle c +\sum_{j = 0}^{i - 1} A_j$ , với$1 \le i < n$
Mảng
Cũng với mảng
Mảng
Để dựng mảng cộng dồn, ta có thể áp dụng định nghĩa ở trên để dựng trực tiếp mảng:
vector<int> buildPrefixSum(const vector<int>& a, int C = 0) {
int n = (int)a.size();
vector<int> prefixSum(n + 1);
prefixSum[0] = C;
for (int i = 0; i < n; i++)
prefixSum[i + 1] = prefixSum[i] + a[i];
return prefixSum;
}
Ngoài ra, thư viện C++ STL cũng cung cấp hàm partial_sum
để phục vụ quá trình dựng mảng cộng dồn, cú pháp của hàm như sau:
partial_sum(first, last, result, binary_op)
Hàm trên sẽ thực hiện tính mảng cộng dồn với toán tử binary_op
trên các container của C++ có iterator trỏ từ [first, last)
và trả mảng cộng dồn sang container bắt đầu từ iterator trỏ về result
.
Có hai lưu ý quan trọng khi sử dụng hàm này:
- Hàm
partial_sum
duyệt qua các phần tử của container theo tính chất của iterator của container đó; vì thế giá trị của mảng cộng dồn sẽ phụ thuộc vào thứ tự xuất hiện của các phần tử trong container đó. - Tham số
binary_op
có thể được để trống. Khi này, toán tử mặc định là phép cộng (+
).
Bạn đọc có thể tham khảo thêm về hàm này tại trang cppreference.
Code minh họa:
void printArray(const vector<int>& arr) {
for (int v : arr) cout << v << " ";
cout << endl;
}
vector<int> a = {3, -1, -4, 1, 5, 9, -2, -6};
int n = (int)a.size();
// Dựng thủ công
vector<int> prefOne = buildPrefixSum(a);
printArray(prefOne); // 0 3 2 -2 -1 4 13 11 5
// Dựng bằng partial_sum
vector<int> prefTwo(n);
partial_sum(a.begin(), a.end(), prefTwo.begin());
printArray(prefTwo); // 3 2 -2 -1 4 13 11 5
Trong cả hai cách trên, độ phức tạp của quá trình dựng là
Tương tự, ta cũng có thể áp dụng định nghĩa để dựng trực tiếp mảng hiệu:
vector<int> buildDifferenceArray(const vector<int>& a) {
int n = (int)a.size();
vector<int> differenceArray(n - 1);
for (int i = 0; i < n - 1; i++)
differenceArray[i] = a[i + 1] - a[i];
return differenceArray;
}
Ngoài ra, thư viện C++ STL cũng cung cấp hàm adjacent_difference
để phục vụ quá trình dựng mảng cộng dồn, cú pháp của hàm như sau:
adjacent_difference(first, last, result, binary_op)
Hàm trên sẽ thực hiện tính mảng hiệu với toán tử binary_op
trên các container của C++ có iterator trỏ từ [first, last)
và trả mảng hiệu sang container bắt đầu từ iterator trỏ về result
.
Các lưu ý ở phần partial_sum
cũng được áp dụng cho hàm này.
Bạn đọc có thể tham khảo thêm về hàm này tại trang cppreference. Code minh họa:
// Dựng thủ công
vector<int> diffOne = buildDifferenceArray(a);
printArray(diffOne);
// -4 -3 5 4 4 -11 -4
// Dựng bằng partial_sum
vector<int> diffTwo(n);
adjacent_difference(a.begin(), a.end(), diffTwo.begin());
printArray(diffTwo);
// 3 -4 -3 5 4 4 -11 -4
Trong cả hai cách trên, độ phức tạp của quá trình dựng là
- Đối với mảng cộng dồn, do ta cần thêm một hằng số
$c$ ở đầu mảng, độ dài của mảng$S(c, A)$ là$n + 1$ , nhiều hơn 1 phần tử so với mảng$A$ gốc. - Ngược lại, mảng hiệu được dựng dựa trên hiệu của hai phần tử liền kề nhau. Tuy nhiên, trong mảng
$A$ chỉ có$n - 1$ cặp như vậy, vì thế độ dài của$D(A)$ là$n - 1$ , ít hơn 1 phần tử so với mảng$A$ gốc.
- Từ một mảng
$A$ bất kỳ, ta sinh được vô hạn mảng cộng dồn$S(c, A)$ từ$A$ . Tuy nhiên, các mảng cộng dồn này chỉ khác nhau ở giá trị$c$ được chọn. - Cũng với mảng
$A$ đó, ta sinh được một và chỉ một mảng hiệu$D(A)$ từ$A$ .
Cho mảng cộng dồn
$S(A_0, D(A)) = A$ -
$D(S(c, A)) = A$ với mọi$c$ thực
Hình dưới đây mô tả rõ hơn mối liên hệ giữa mảng gốc, mảng hiệu và mảng cộng dồn sinh ra từ nó:
Hàm partial_sum
và adjacent_difference
trong C++ STL cũng tuân theo quy tắc này trên. Tuy nhiên, các thao tác trên hai hàm này có phần phức tạp hơn so với thao tác trên mảng mà ta cài đặt thủ công.
Mảng cộng dồn có một tính chất quan trọng: các phần tử được cộng lại chồng chất lên nhau một cách liên tiếp, vì thế, với mọi nửa khoảng
Chứng minh:
Theo định nghĩa:
Khi này:
Trong đa số trường hợp, mảng cộng dồn thường được sử dụng nếu bài toán yêu cầu tính tổng một đoạn con nhiều lần liên tiếp. Dưới đây, ta sẽ đề cập một số bài toán có điều kiện trên.
Nguồn: CSES - Maximum Subarray Sum
Đề bài: Cho một mảng
Trước hết, ta tạo mảng
Nếu ta chạy
Độ phức tạp của cách trên là
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200003;
const long long INF = 1e18;
int n, a[MAXN];
long long prefSum[MAXN], prefMin[MAXN], ans = -INF;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
prefSum[0] = prefMin[0] = 0;
for (int i = 1; i <= n; i++)
prefSum[i] = prefSum[i - 1] + a[i], prefMin[i] = min(prefMin[i - 1], prefSum[i]);
for (int i = 1; i <= n; i++)
ans = max(ans, prefSum[i] - prefMin[i - 1]);
cout << ans;
}
Lưu ý, ta có thể thu gọn prefSum
và prefMin
thành một biến duy nhất để tối ưu bộ nhớ sử dụng.
Bên cạnh cách giải đã đề cập, bài toán này cũng có thể giải bằng phương pháp quy hoạch động hoặc chia để trị.
Giả sử, ta cần cộng thêm một lượng
- Nếu
$A_i$ và$A_{i + 1}$ đều nằm ngoài$[l, r]$ $\Rightarrow$ Giá trị của hai phần tử không đổi$\Rightarrow$ $D_i$ không đổi - Nếu
$A_i$ và$A_{i + 1}$ đều nằm trong$[l, r]$ $\Rightarrow$ Giá trị của hai phần tử đều được cộng một lượng$k$ $\Rightarrow$ $D_i$ không đổi - Nếu chỉ một trong
$A_i$ hoặc$A_{i + 1}$ nằm trong$[l, r]$ $\Rightarrow$ Giá trị của một phần tử giữ nguyên còn phần tử còn lại được cộng một lượng$k$ $\Rightarrow$ $D_i$ thay đổi
Chỉ duy nhất trường hợp cuối cùng ta cần tác động trực tiếp lên
Nguồn: Codeforces - Karen and Coffee
Đề bài: Cho một mảng
Sau khi cập nhật xong, trả lời
Giới hạn:
Do điều kiện
Gọi
Để trả lời câu hỏi, ta có thể hình dung mỗi chỉ số trong đoạn
Độ phức tạp thời gian và không gian của cách này đều là
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200003;
int n, k, q, d[MAXN], a[MAXN], s[MAXN];
void update(int l, int r) {
++d[l], --d[r + 1];
}
void buildPrefixSum() {
a[0] = s[0] = 0;
for (int i = 1; i < MAXN; i++) {
a[i] = a[i - 1] + d[i];
s[i] = s[i - 1] + (a[i] >= k);
}
}
int query(int a, int b) {
return s[b] - s[a - 1];
}
int main() {
cin >> n >> k >> q;
for (int i = 0; i < n; i++) {
int l, r; cin >> l >> r;
update(l, r);
}
buildPrefixSum();
for (int i = 0; i < q; i++) {
int a, b; cin >> a >> b;
cout << query(a, b) << endl;
}
}
Ta có thể mở rộng mảng cộng dồn và mảng hiệu để thao tác trên mảng nhiều chiều.
Cho mảng hai chiều
Các phần tử trong mảng cộng dồn lưu tổng của toàn bộ phần tử chứa trong hình chữ nhật
Từ công thức quy ước trên, ta thực hiện biến đổi sau để dựng mảng cộng dồn:
Để hình dung rõ hơn công thức biến đổi trên, bạn đọc có thể tham khảo hình ảnh dưới:
Các phần tử |
Code dưới đây dựng mảng cộng dồn hai chiều:
vector< vector<int> > build2DPrefixSum(const vector< vector<int> >& a) {
int m = (int)a.size(), n = (int)a[0].size();
vector< vector<int> > prefixSum(m + 1, vector<int> (n + 1, 0));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[i - 1][j - 1]; // ta truy cập a(i - 1, j - 1) do mảng A là 0-indexed
return prefixSum;
}
Để tính tổng của toàn bộ các phần tử nằm trong hình chữ nhật có góc trái trên là
Phần chứng minh công thức trên xin được nhường lại cho bạn đọc. Hình ảnh dưới minh họa vì sao công thức trên cho kết quả chính xác:
Các phần tử |
Giả sử ta có mảng
Công thức sau được sử dụng để dựng mảng cộng dồn 3 chiều:
Tương tự, ta tính tổng các phần tử trong không gian
Hai công thức trên được xây dựng thông qua phương pháp bao hàm - loại trừ. Bạn đọc có thể tham khảo bài viết Bao hàm - Loại trừ trên VNOI Wiki để hiểu rõ hơn lý do có được công thức trên.
Ta cũng có thể áp dụng phương pháp này để mở rộng cho các mảng
Trước khi bắt đầu xây dựng mảng hiệu 2 chiều, ta cần định nghĩa thêm 2 khái niệm sau cho một mảng
-
$D_{hàng}(A)$ gồm$m$ hàng, hàng thứ$i$ biểu thị mảng hiệu của mảng gồm toàn bộ phần tử nằm trên hàng đó. -
$D_{cột}(A)$ gồm$n$ cột, cột thứ$i$ biểu thị mảng hiệu của mảng gồm toàn bộ phần tử nằm trên cột đó.
Trong không gian 1 chiều, ta thấy được
Đặt
$$ \begin{align*} D_{i, j} &= [D_{cột}(D_{hàng}(A))]{i, j} \ &= [D{hàng}(A_i)]j - [D{hàng}(A_{i - 1})]j \ &= (A{i, j} - A_{i, j - 1}) - (A_{i - 1, j} - A_{i - 1, j - 1}) \ &= A_{i, j} - A_{i, j - 1} - A_{i - 1, j} + A_{i - 1, j - 1} \end{align*} $$
Mảng
$$ \begin{align*} \displaystyle S(D){i,j} &= \sum{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} D_{t_i,t_j}\ &=\sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} (A_{t_i, t_j} - A_{t_i, t_j - 1} - A_{t_i - 1, t_j} + A_{t_i - 1, t_j - 1})\ &=\sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} A_{t_i, t_j} - \sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} A_{t_i, t_j - 1} - \sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} A_{t_i - 1, t_j} + \sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} A_{t_i - 1, t_j - 1}\ &=\sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} A_{t_i, t_j} - \sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j-1} A_{t_i, t_j} - \sum_{t_i,=,1}^{i-1} \sum_{t_j,=,1}^{j} A_{t_i, t_j} + \sum_{t_i,=,1}^{i-1} \sum_{t_j,=,1}^{j-1} A_{t_i, t_j}\ &= S_{i,j} - S_{i-1,j} - S_{i,j-1} + S_{i-1,j-1} \ &= {A'}_{i, j} \ \end{align*} $$
Ta kết luận rằng
Từ các quan sát trên, ta có thể dựng mảng hiệu của
- Sử dụng trực tiếp công thức:
$D_{i, j} = A_{i, j} - A_{i, j - 1} - A_{i - 1, j} + A_{i - 1, j - 1}$ - Tính
$D_{hàng}$ cho từng hàng của$A$ và gán kết quả vào$A'$ , sau đó tính$D_{cột}$ cho từng cột của$A'$ .
Code dưới đây dựng mảng hiệu 2 chiều
vector< vector<int> > build2DDifferenceArray(const vector< vector<int> >& a) {
int m = (int)a.size(), n = (int)a[0].size();
vector< vector<int> > differenceArray(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
differenceArray[i][j] = a[i][j];
if (i > 0) differenceArray[i][j] -= a[i - 1][j];
if (j > 0) differenceArray[i][j] -= a[i][j - 1];
if (i > 0 && j > 0) differenceArray[i][j] += a[i - 1][j - 1];
}
}
return differenceArray;
}
Quay lại bài toán cũ trong không gian 1 chiều: làm thế nào để ta tăng thêm một lượng
Từ nhận xét trên, ta thấy chỉ có 4 phần tử của
Cũng như mảng cộng dồn, ta cũng có thể dựng mảng hiệu của các mảng trong không gian 3 chiều. Tương tự, nếu ta coi
Để xử lý truy vấn cập nhật toàn bộ phần tử trong không gian
Hình trên minh họa những vị trí mà ta cần cập nhật trên mảng hiệu. Tương tự mảng cộng dồn, phương pháp bao hàm - loại trừ được áp dụng để đưa đến kết luận này.
Trong các ví dụ đã đề cập, các bài toán chúng ta phải giải đều không có truy vấn cập nhật hoặc toàn bộ truy vấn cập nhật được thực hiện trước truy vấn hỏi. Tuy nhiên, trong một số bài toán yêu cầu phải thực hiện xen kẽ hai loại truy vấn này, ta cần sử dụng các cấu trúc dữ liệu để giải quyết hiệu quả các truy vấn này.
Có hai dạng bài toán liên quan đến mảng cộng dồn và mảng hiệu:
-
Dạng 1: Cập nhật giá trị của
$A_i$ hoặc tính tổng của$i$ phần tử đầu tiên. -
Dạng 2: Cập nhật toàn bộ giá trị từ
$A_i$ đến$A_j$ $(i \le j)$ hoặc cho biết giá trị hiện tại của$A_i$ .
Nếu bài toán chỉ xử lý một trong hai dạng nói trên, ta có thể áp dụng cấu trúc dữ liệu Binary Indexed Tree để giải quyết các truy vấn trên. Độ phức tạp của từng truy vấn sẽ phụ thuộc vào số chiều của mảng, thí dụ, thao tác trên mảng 1D sẽ cho độ phức tạp
Trong một số bài toán yêu cầu xử lý kết hợp 2 dạng (cập nhật đoạn và tính tổng đoạn), ta thường áp dụng Segment Tree có lazy propagation (cập nhật lười). Mặc dù có chung độ phức tạp, cách cài đặt này thường khó hơn, có thời gian chạy lâu hơn và dùng nhiều bộ nhớ hơn so với cài đặt Binary Indexed Tree. Nếu ta làm việc trên mảng 1 chiều, ta cũng có thể biến đổi hệ thức giữa mảng hiệu và mảng cộng dồn để cài đặt trực tiếp BIT làm việc trên các truy vấn này. Bạn đọc có thể tham khảo thêm cách cài đặt này tại đây.
Codeforces - Little Girl and Maximum Sum
Codeforces Gym - 319055E (lưu ý: để xem nội dung bài tập cần tham gia nhóm tại link đây)
VNOJ có phân loại riêng các bài tập về mảng cộng dồn, bạn đọc có thể tham khảo tại đây.
WCIPEG - Prefix sum array and difference array