¶ Mảng cộng dồn và mảng hiệu
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
¶ Khái niệm
¶ Mảng cộng dồn (prefix sum)
Cho một mảng có phần tử được đánh số từ đến , ta dựng mảng theo quy tắc sau:
- , với là một hằng số thực
- , với
Mảng được gọi là mảng cộng dồn (tiền tố) theo của , gọi cách khác là prefix sum của . Từ một mảng , ta có thể sinh ra vô hạn mảng bằng cách chọn một số thực tùy ý; trên thực tế, ta thường chọn để thuận tiện hơn khi tính toán.
¶ Mảng hiệu (difference array)
Cũng với mảng , ta có thể dựng mảng theo quy tắc: .
Mảng được gọi là mảng hiệu của , có tên tiếng Anh là difference array.
¶ Cài đặt
¶ Mảng cộng dồn
Để 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_sumduyệ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_opcó 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à .
¶ Mảng hiệu
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à .
¶ Tính chất
¶ Độ dài mảng
- Đối với mảng cộng dồn, do ta cần thêm một hằng số ở đầu mảng, độ dài của mảng là , nhiều hơn 1 phần tử so với mảng 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 chỉ có cặp như vậy, vì thế độ dài của là , ít hơn 1 phần tử so với mảng gốc.
¶ Tính riêng biệt
- Từ một mảng bất kỳ, ta sinh được vô hạn mảng cộng dồn từ . Tuy nhiên, các mảng cộng dồn này chỉ khác nhau ở giá trị được chọn.
- Cũng với mảng đó, ta sinh được một và chỉ một mảng hiệu từ .
¶ Liên hệ giữa mảng cộng dồn và mảng hiệu
Cho mảng cộng dồn và mảng hiệu , ta có thể dễ dàng khôi phục nội dung của mảng thông qua các phép sau:
- với mọi 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.
¶ Ứng dụng của mảng cộng dồn
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 , ta chỉ cần tính để tính tổng của các phần tử . Việc trừ này cũng sẽ khử đi hằng số của , vì thế ta có thể dùng bất kỳ mảng nào được sinh từ để tính tổ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.
¶ Bài toán minh họa
Nguồn: CSES - Maximum Subarray Sum
Đề bài: Cho một mảng gồm phần tử. Tìm đoạn con khác rỗng có tổng lớn nhất. Giới hạn: ,
Trước hết, ta tạo mảng để lưu mảng cộng dồn của . Giả sử với cố định, ta cần tìm sao cho tổng các phần tử trong nửa khoảng đạt cực đại. Ta viết lại bài toán theo công thức sau:
Nếu ta chạy từ đến , ta có thể cập nhật cuốn chiếu theo từng ; việc này cho phép chúng ta tính với độ phức tạp . Đáp án của bài toán là với .
Độ phức tạp của cách trên là . Code tham khảo:
#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ị.
¶ Ứng dụng của mảng hiệu
Giả sử, ta cần cộng thêm một lượng vào một đoạn con của mảng . Thay vì cộng lần lượt từng phần tử với độ phức tạp , ta có thể dựng mảng hiệu và cập nhật trên đó với độ phức tạp . Dựng mảng hiệu từ lưu trữ chênh lệch của các cặp phần tử liền kề nhau, ta chia các trường hợp sau để nhận xét:
- Nếu và đều nằm ngoài Giá trị của hai phần tử không đổi không đổi
- Nếu và đều nằm trong Giá trị của hai phần tử đều được cộng một lượng không đổi
- Nếu chỉ một trong hoặc nằm trong 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 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 . Nhận thấy, trường hợp cuối chỉ thỏa khi hoặc , ta chỉ cần tác động trực tiếp lên và để cập nhật đoạn. Sau khi cập nhật hoàn tất, ta áp dụng tính chất để lấy giá trị cuối cùng của .
¶ Bài toán minh họa
Nguồn: Codeforces - Karen and Coffee
Đề bài: Cho một mảng có vô số phần tử mang giá trị . Có truy vấn cập nhật, mỗi truy vấn yêu cầu cập nhật toàn bộ phần tử từ đến thêm .
Sau khi cập nhật xong, trả lời câu hỏi với nội dung sau: có bao nhiêu vị trí thỏa và ?
Giới hạn:
Do điều kiện của đề bài, mảng sẽ chỉ lưu trữ tối đa 200 nghìn phần tử, toàn bộ phần tử này đều có chỉ số dương, vì thế ta sẽ đơn thuần lưu 2 mảng này dưới dạng mảng thường.
Gọi là mảng hiệu của . Để xử lý truy vấn cập nhật, ta chỉ cần cập nhật giá trị của mảng tại 2 biên và bằng cách tăng thêm và trừ khỏi . Sau khi xử lý toàn bộ truy vấn cập nhật, ta sử dụng hệ thức để cập nhật lại giá trị của mảng .
Để trả lời câu hỏi, ta có thể hình dung mỗi chỉ số trong đoạn mang giá trị nếu thỏa điều kiện đề bài và nếu không thỏa; số chỉ số thỏa mãn cũng chỉ là tổng của các phần tử nằm trong đoạn . Từ tính chất này, ta có thể ứng dụng mảng cộng dồn để trả lời nhau câu hỏi trong . Ta đặt mảng đánh dấu giá trị tương ứng có thỏa điều kiện không, rồi dựng mảng cộng dồn trên . Đáp án của mỗi câu hỏi sẽ là kết quả của phép tính .
Độ phức tạp thời gian và không gian của cách này đều là . Code tham khảo:
#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;
}
}
¶ Mở rộng sang mảng nhiều chiều
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.
¶ Mảng cộng dồn hai chiều
Cho mảng hai chiều có kích thước (chỉ số hàng và cột đầu tiên đều là 1), mảng cộng dồn được dựng theo công thức sau:
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 .
Điểm khác biệt so với mảng cộng dồn 1 chiều ở đây là sự lược bỏ của hằng số , ta ngầm quy ước: với nguyên không âm khi dựng mảng cộng dồn.
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ử tô màu xanh nhạt được đánh dấu 1 lần, tô màu xanh đậm được đánh dấu tới 2 lần |
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à và góc phải dưới , ta biến đổi tương tự để thu được công thức tính sau:
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ử tô màu đỏ bị trừ tới 2 lần, vì thế cần phải cộng bù lại |
¶ Mảng cộng dồn ba chiều
Giả sử ta có mảng trong không gian 3 chiều với kích thước , ta dựng mảng theo quy tắc sau: $$S_{i, j, k}=\displaystyle \sum_{t_i,=,1}^{i} \sum_{t_j,=,1}^{j} \sum_{t_k,=,1}^{k} A_{t_i,t_j,t_k}$$
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 qua công thức sau:
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 -chiều. Tuy nhiên, do số lượng bài toán liên quan đến mảng trong không gian từ 4 chiều trở lên là cực hiếm, mảng cộng dồn trong không gian này gần như không có ứng dụng thực tiễn. Vì thế, bài viết xin giới hạn lại tại mảng cộng dồn trong không gian 3 chiều trở xuống.
¶ Mảng hiệu hai chiều
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 hai chiều có kích thước :
- gồm hàng, hàng thứ 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 đó.
- gồm cột, cột thứ 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ính chất này được áp dụng cho mảng 2 chiều, ta tạo mảng thỏa: với dương và với hoặc . Mảng này đánh số theo dạng 0-indexed và có kích thước là . Khi này, mảng hiệu của sẽ là mảng thỏa .
Đặt , khi này, ta có:
Mảng có giá trị như sau:
Ta kết luận rằng , mảng ta vừa dựng chính là mảng hiệu của .
Từ các quan sát trên, ta có thể dựng mảng hiệu của bằng hai cách:
- Sử dụng trực tiếp công thức:
- Tính cho từng hàng của và gán kết quả vào , sau đó tính cho từng cột của .
Code dưới đây dựng mảng hiệu 2 chiều theo theo cách thứ nhất:
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 lên toàn bộ phần tử trong lưới một cách hiệu quả? Khi ta tính cho từng hàng của , ta nhận thấy chỉ giá trị của phần tử ở biên trái (tại ) và biên phải (tại ). Tiếp tục tính cho từng cột của mảng , quan sát tương tự cho thấy chỉ phần tử tại và sẽ bị tác động bởi thao tác cập nhật này.
Từ nhận xét trên, ta thấy chỉ có 4 phần tử của sẽ bị tác động bởi thao tác này là tọa độ , , và - trong đó, phần tử tại và tăng thêm lượng , phần tử tại và trừ đi lượng . Ta dễ dàng cập nhật đoạn trên mảng hai chiều với độ phức tạp .
¶ Mảng hiệu ba chiều
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 là mảng sinh ra mảng cộng dồn , ta có công thức dựng sau:
Để xử lý truy vấn cập nhật toàn bộ phần tử trong không gian , ta cần cập nhật giá trị tại vị trí, các vị trí đều nằm tại biên của không gian. Nếu ta coi mảng -chiều như một hình lập phương chứa số, vị trí cần cập nhật sẽ tương ứng với đỉnh của hình lập phương đại diện cho không gian cần cập nhật. Ta sẽ tô xen kẽ các đỉnh này theo hai màu đen - trắng, đỉnh có tọa độ được tô màu trắng. Phần tử ứng với các đỉnh trắng được cộng thêm lượng , ngược lại, phần tử ứng với đỉnh đen thì trừ đi lượng .
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.
¶ Mở rộng sang mảng động
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 hoặc tính tổng của phần tử đầu tiên.
- Dạng 2: Cập nhật toàn bộ giá trị từ đến hoặc cho biết giá trị hiện tại của .
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 còn trên mảng 2D sẽ là .
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.
¶ Bài tập
¶ Mảng cộng dồn 1 chiều
¶ Mảng hiệu 1 chiều
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)
¶ Mảng cộng dồn nhiều chiều
¶ Mảng hiệu nhiều chiều
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.
¶ References
WCIPEG - Prefix sum array and difference array