Quy hoạch động 5.5: Mảng tổng tiền tố và Mảng hiệu (phần 1)
I. Giới thiệu chung
Những bài toán trên mảng là chủ đề rất quen thuộc ở các kì thi lập trình. Mảng tổng tiền tố và Mảng hiệu là hai kĩ thuật bổ trợ, giúp đẩy nhanh tốc độ tính toán của một số thao tác trên mảng. Trong chuyên đề này, chúng ta sẽ cùng tìm hiểu về cách xây dựng và những ứng dụng của hai kĩ thuật nói trên.
1. Khái niệm
Mảng tổng tiền tố
Với mảng gồm phần tử ta xây dựng một mảng theo quy tắc sau:
- với là một hằng số thực.
- .
Khi đó, mảng được gọi là mảng tổng tiền tố (prefix sum array) của . Từ một mảng ta có thể sinh ra vô số mảng bằng cách chọn một hằng số tùy ý. Nhưng trên thực tế, ta thường chọn để thuận tiện hơn khi tính toán.
<center>Mảng hiệu
Cũng với mảng ta có thể xây dựng thêm một mảng theo quy tắc như sau:
Mảng được gọi là mảng hiệu (difference array) của .
<center>2. Phương pháp cài đặt
Mảng tổng tiền tố
Để xây dựng mảng tổng tiền tố, ta có thể áp dụng đúng định nghĩa để cài đặt trên mảng:
vector < int > build_prefix_sum(int n, int c, vector < int >& a)
{
vector < int > sum(n + 1);
sum[0] = c; // Thường thì c = 0.
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + a[i];
return sum;
}
Hoặc ta có thể áp dụng hàm partial_sum()
trong STL C++, cú pháp hàm này như sau:
partial_sum(first, last, result, binary_op);
Hàm này có ý nghĩa xây dựng tổng tiền tố cho các phần tử nằm trong phạm vi hai iterator [first, last)
của một container, và trả mảng tổng tiền tố sang mảng kết quả, bắt đầu từ vị trí có iterator là result
. Quá trình tính toán sẽ được thực hiện bằng toán tử binary_op
(xem thêm minh họa về hàm này tại đây), nếu để trống thì mặc định là toán tử +
:
vector < int > build_prefix_sum(int n, int c, vector < int >& a)
{
vector < int > sum(n + 1);
sum[0] = c; // Thường thì c = 0.
partial_sum(a.begin() + 1, a.end(), sum.begin() + 1);
return sum;
}
Độ phức tạp của quá trình dựng mảng tổng tiền tố theo cả hai cách là .
Mảng hiệu
Tương tự như mảng tổng tiền tố, ta cũng có thể xây dựng Mảng hiệu theo định nghĩa:
vector < int > build_diff_array(int n, vector < int >& a)
{
vector < int > diff(n + 1);
diff[1] = a[1];
for (int i = 2; i <= n; ++i)
diff[i] = a[i] - a[i - 1];
return diff;
}
Ngoài ra ta có thể sử dụng hàm adjacent_difference()
được cung cấp bởi thư viện STL C++, với cú pháp như sau:
adjacent_difference(first, last, result, binary_op);
Hàm này sẽ thực hiện tính mảng hiệu cho các phần tử có iterator trong đoạn [first, last)
của một container, và trả về mảng hiệu sang container từ vị trí có iterator là result
. Tuy nhiên toán tử mặc định sử dụng trong hàm sẽ là toán tử -
(xem thêm về hàm này tại đây):
vector < int > build_diff_array(int n, vector < int >& a)
{
vector < int > diff(n);
adjacent_difference(a.begin() + 1, a.end(), diff.begin() + 1);
return diff;
}
Độ phức tạp của quá trình xây dựng mảng hiệu theo hai cách trên đều là .
3. Tính chất
Độ dài mảng
- Mảng tổng tiền tố có thêm một phần tử phụ nên độ dài của nó sẽ nhiều hơn độ dài mảng gốc phần tử - tức là .
- Mảng hiệu lại được dựng bằng hiệu giữa hai phần tử kề nhau, mà chỉ có cặp như vậy, nên độ dài của là (tính cả phần tử ).
Tính riêng biệt
- Từ một mảng với mỗi hằng số khác nhau ta lại tạo ra được một mảng tổng tiền tố khác nhau. Tuy nhiên, các mảng tổng tiền tố này chỉ khác nhau duy nhất ở giá trị .
- Trái lại, cũng từ mảng đó, ta xây dựng được một và chỉ một mảng hiệu.
Liên hệ giữa Mảng tổng tiền tố và Mảng hiệu
Với mảng cộng dồn và mảng hiệu ta có thể khôi phục được mảng ban đầu thông qua hai cách:
- .
- với mọi giá trị .
Xem hình minh họa dưới đây để hiểu rõ mối liên kết nói trên:
Hàm partial_sum()
và adjacent_difference()
trong C++ STL cũng tuân theo quy tắc nêu 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.
II. Ứng dụng của mảng tổng tiền tố
1. Ứng dụng cơ bản
Mảng tổng tiền tố có một ứng dụng quan trọng trong các bài toán trên dãy số. Kĩ thuật này giúp chúng ta tính nhanh ra tổng các số trên một đoạn trong thời gian chỉ ứng dụng rất nhiều trong các bài toán lập trình thi đấu.
Nội dung bài toán cơ bản có thể phát biểu như sau:
Cho một dãy số gồm phần tử . Cần trả lời truy vấn, mỗi truy vấn có dạng yêu cầu đưa ra tổng của các số có vị trí thuộc đoạn của dãy số.
Input:
- Dòng đầu tiên chứa hai số nguyên dương và - độ dài dãy số và số truy vấn.
- Dòng thứ hai chứa số nguyên phân tách nhau bởi dấu cách.
- Trên dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và thể hiện một truy vấn.
Ràng buộc:
- .
- .
- .
Output:
- Ứng với mỗi truy vấn, in ra một số nguyên là tổng các số trong đoạn tương ứng. Kết quả mỗi truy vấn in ra trên một dòng.
Sample Input:
5 3
1 2 3 4 5
1 5
2 4
3 3
Sample Output:
15
9
3
Ý tưởng
Cách làm mà ai cũng có thể nhận ra là ứng với mỗi truy vấn, ta duyệt lại trên mảng từ vị trí tới vị trí và tính tổng:
Cách làm này có độ phức tạp tổng quát là . Do số truy vấn có thể lên tới nên chắc chắn cách này bị chạy quá thời gian.
Ta sẽ xây dựng một mảng là tổng tiền tố của mảng .
Khi đó, tổng của các số thuộc đoạn trên mảng sẽ được tính theo công thức:
Việc trừ này cũng sẽ khử đi hằng số nên ta có thể áp dụng bất kì mảng tổng tiền tố nào được sinh ra từ để tính tổng đoạn con. Và nhờ vào công thức này, mỗi truy vấn có thể được trả lời chỉ trong . Các bạn chỉ cần khởi tạo trước mảng tổng tiền tố trong mà thôi. Do tính chất cộng từ trước ra sau, nên kĩ thuật này còn được gọi là mảng cộng dồn.
Cài đặt
#include <bits/stdc++.h>
using namespace std;
long long query(int l, int r, vector < long long >& sum)
{
return sum[r] - sum[l - 1];
}
main()
{
int n, q;
cin >> n;
vector < long long > sum(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
long long x;
cin >> x;
sum[i] = sum[i - 1] + x;
}
while (q--)
{
int l, r;
cin >> l >> r;
cout << query(l, r, sum) << endl;
}
return 0;
}
2. Mảng tổng tiền tố hai chiều
Mảng tổng tiền tố có thể được phát triển lên để sử dụng trên các ma trận hai chiều kích thước dùng để tính tổng một hình chữ nhật con có kích thước bất kì trong ma trận đó, thông qua kĩ thuật Bao hàm - Loại trừ.
Bài toán được phát biểu khá tương tự:
Cho một ma trận kích thước các hàng được đánh số từ tới từ trên xuống, các cột được đánh số từ tới từ trái qua phải. Ô nằm trên giao của hàng cột gọi là ô trên đó có điền số nguyên .
Cần trả lời truy vấn, mỗi truy vấn có dạng yêu cầu đưa ra tổng của các số thuộc hình chữ nhật có góc trái trên ở tọa độ và góc phải dưới ở tọa độ
Input:
- Dòng đầu tiên chứa ba số nguyên dương và - kích thước ma trận và số truy vấn.
- Trên dòng tiếp theo, dòng thứ chứa số nguyên phân tách nhau bởi dấu cách - thể hiện hàng của ma trận.
- Trên dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương thể hiện một truy vấn.
Ràng buộc:
- .
- .
- .
Output:
- Ứng với mỗi truy vấn, in ra một số nguyên là tổng các số trong hình chữ nhật con tương ứng. Kết quả mỗi truy vấn in ra trên một dòng.
Sample Input:
5 4 3
1 3 2 4
5 7 8 9
1 4 2 5
2 4 -8 9
-5 -1 -2 -3
1 1 3 3
2 3 5 4
1 1 5 4
Sample Output:
33
20
47
Ý tưởng
Ta sử dụng một mảng hai chiều để lưu tổng tiền tố của ma trận . Gọi là tổng các số thuộc hình chữ nhật có góc trái trên là góc phải dưới là .
Giả sử ta cần tính tổng hình chữ nhật như hình bên dưới:
Hình 1
Nhận thấy, tổng hình chữ nhật có thể được tạo thành bằng cách gộp tổng hai hình chữ nhật và lại, rồi cộng thêm giá trị :
Hình 2
Tuy nhiên, như vậy thì tổng các số trong hình chữ nhật sẽ bị tính thừa một lần, vì thế ta trừ bớt nó đi:
Hình 3
Tổng hợp lại công thức ở cả ba hình ta rút ra công thức xây dựng :
Tiếp theo ta xây dựng công thức để tìm ra tổng của một hình chữ nhật con .
Hình 4
Nhận thấy, đã là tổng hình chữ nhật con nên ta chỉ cần thêm bớt sao cho đạt được hình chữ nhật mong muốn. Ta sẽ trừ bớt đi tổng của hai hình chữ nhật con và :
Hình 5
Tuy nhiên, phần hình chữ nhật lại bị trừ thừa thêm lần. Do đó ta phải cộng lại một lần phần này vào kết quả.
Hình 6
Tổng hợp lại công thức, ta có cách lấy tổng của một hình chữ nhật con như sau:
Việc chuẩn bị trước mảng tổng tiền tố sẽ mất nhưng trả lời truy vấn thì chỉ còn
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
long long query(int x1, int y1, int x2, int y2,
vector < vector < long long > >& sum)
{
return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
main()
{
int m, n, q;
cin >> m >> n >> q;
vector < vector < long long > > sum(m + 1, vector < long long >(n + 1, 0));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
{
int x;
cin >> x;
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;
}
while (q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << query(x1, y1, x2, y2, sum) << endl;
}
}
3. Mảng tổng tiền tố 3 chiều (đọc thêm)
Giả sử ta có mảng trong không gian ba chiều với kích thước thì mảng tổng tiền tố của nó được xây dựng theo quy tắc:
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 thông qua Bao hàm - Loại trừ:
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.
4. Một số bài tập minh họa
Bài toán 1: Phần thưởng
Đề bài
Bạn Hoa tham gia một trò chơi trên mạng và may mắn trở thành người chiến thắng. Tuy nhiên, luật trao thưởng của trò chơi này lại khá kì quặc. Các phần thưởng được xếp trên một bảng ô vuông đơn vị có kích thước ô vuông nằm ở giao của hàng cột chứa phần thưởng có giá trị là .
Minh họa bảng phần thưởng kích thước
Để nhận thưởng, Hoa sẽ phải điều khiển một nhân vật xuất phát từ vị trí trên bảng ô vuông, đi tới ô và chỉ được sử dụng các bước đi xuống dưới hoặc sang phải. Tổng giá trị phần thưởng của các ô mà nhân vật đi qua sẽ là phần thưởng mà Hoa nhận được.
Yêu cầu: Hãy tính tổng giá trị phần thưởng lớn nhất mà Hoa có thể nhận được?
Input:
- Dòng đầu tiên chứa số nguyên dương .
- Hai dòng tiếp theo, mỗi dòng chứa số nguyên dương thể hiện một hàng của bảng phần thưởng.
Ràng buộc:
- .
- .
Output:
- Số nguyên duy nhất là tổng giá trị phần thưởng lớn nhất mà Hoa nhận được.
Sample Input:
7
1 3 7 3 2 5 6
9 10 5 7 7 9 8
Sample Output:
56
Giải thích:
Các ô màu đỏ chính là đường đi mà Hoa sẽ chọn:
Ý tưởng
Nhận xét thấy, một khi Hoa đã di chuyển từ hàng thứ nhất xuống hàng thứ hai thì sẽ phải đi tiếp tới cuối hàng thứ hai, do chỉ được phép đi sang phải hoặc xuống dưới. Vì thế, kết quả bài toán sẽ là:
Với các bộ dữ liệu nhỏ, ta chỉ cần duyệt mọi vị trí ứng với mỗi dùng thêm hai vòng lặp để tính tổng đoạn và rồi lấy tổng lớn nhất làm kết quả. Độ phức tạp giải thuật là .
Nhưng để làm được tối đa điểm của bài toán, cần xây dựng trước mảng tổng tiền tố là tổng các số trên hàng từ cột tới cột . Sau đó, việc lấy tổng của đoạn trên hàng và đoạn trên hàng có thể thực hiện trong với mỗi giá trị từ tới . Tới đây thu được giải thuật .
Cài đặt
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
typedef int matrix[3][maxn];
int n;
matrix prefix_sum;
void enter()
{
cin >> n;
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= n; ++j)
{
int a;
cin >> a;
prefix_sum[i][j] = prefix_sum[i][j - 1] + a;
}
}
void solution()
{
int res = 0;
for (int j = 1; j <= n; ++j)
{
int first_row_sum = prefix_sum[1][j];
int second_row_sum = prefix_sum[2][n] - prefix_sum[2][j - 1];
res = max(res, first_row_sum + second_row_sum);
}
cout << res;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
enter();
solution();
return 0;
}
Bài toán 2: Hình vuông con
Đề bài
Một bảng hình chữ nhật được chia thành lưới ô vuông đơn vị kích thước . Các hàng của bảng được đánh số từ tới từ trên xuống dưới; các cột của bảng được đánh số từ tới từ trái qua phải. Ô nằm trên hàng cột của bảng được gọi là ô và có ghi giá trị . Một hình vuông con của bảng là hình vuông chiếm chọn một số ô của bảng.
Yêu cầu: Với số nguyên dương cho trước, hãy chọn ra một hình vuông con kích thước sao cho giá trị của số nhỏ nhất trong hình vuông con là lớn nhất?
Input:
- Dòng đầu tiên chứa ba số nguyên dương .
- Trên dòng tiếp theo, dòng thứ chứa số nguyên dương thể hiện hàng thứ của bảng số.
Ràng buộc:
- .
- .
- .
Output:
- Chứa một số nguyên duy nhất là giá trị của số nhỏ nhất trong hình vuông thỏa mãn yêu cầu của đề bài.
Sample Input:
5 5 2
1 11 2 3 3
9 9 2 3 3
2 2 2 2 2
1 2 2 5 6
4 10 2 7 8
Sample Output:
5
Giải thích:
Hình vuông con với tọa độ góc trái trên và góc phải dưới là hình vuông thỏa mãn đề bài.
Ý tưởng
Gọi giá trị của số nhỏ nhất trong hình vuông tìm được là .
Nếu gọi là một hàm kiểm tra có tồn tại hình vuông nào mà giá trị nhỏ nhất là hay không, thì ta thấy khi càng tăng lên, khả năng hàm càng giảm đi (vì càng to thì càng khó tồn tại hình vuông nhận nó làm giá trị nhỏ nhất). Từ đây, ta thấy là một hàm thỏa mãn Định lý chính của Tìm kiếm nhị phân, giá trị lớn nhất thỏa mãn có thể tìm được thông qua Tìm kiếm nhị phân trên tập kết quả.
Xét các giá trị ta xây dựng hàm như sau:
- Xây dựng một bảng hai chiều với ý nghĩa: Nếu thì ngược lại . Lúc này, nếu một ma trận con trên bảng có giá trị nhỏ nhất là thì tổng của ma trận con tương ứng trên bảng sẽ đúng bằng (nghĩa là tất cả các số trong ma trận con đó đều ).
- Xác định xem có tồn tại ma trận con nào thỏa mãn tổng của ma trận con tương ứng trên bảng hay không? Bước này ta có thể áp dụng quy hoạch động mảng tổng tiền tố hai chiều trên bảng .
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
void enter(int &m, int &n, int &k, vector < vector < int > >& a)
{
cin >> m >> n >> k;
a = vector < vector < int > >(m + 1, vector < int >(n + 1));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
}
int get_sum(int x1, int y1, int x2, int y2, vector < vector < int > >& sum)
{
return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
// Tạo mảng s[i][j] là số lượng giá trị a[i][j] >= min_value
// trong hình chữ nhật (1, 1, i, j).
vector < vector < int > > create_table(int m, int n, vector < vector < int > >& a,
int min_value)
{
// Tạo mảng tổng tiền tố s[i][j].
vector < vector < int > > s(m + 1, vector < int >(n + 1, 0));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] >= min_value);
return s;
}
// Kiểm tra xem có tồn tại hình vuông k * k nào mà các số trong đó đều
// lớn hơn hoặc bằng min_value hay không.
bool check(int m, int n, int k, vector < vector < int > >& a, int min_value)
{
vector < vector < int > > sum = create_table(m, n, a, min_value);
for (int i = 1; i <= m - k + 1; ++i)
for (int j = 1; j <= n - k + 1; ++j)
{
int ii = i + k - 1, jj = j + k - 1;
if (get_sum(i, j, ii, jj, sum) == k * k)
return true;
}
return false;
}
// Chặt nhị phân tìm giá trị nhỏ nhất tối đa trong các hình vuông kích thước k * k.
void solution(int m, int n, int k, vector < vector < int > >& a)
{
int l = 1, r = 1000000, res = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(m, n, k, a, mid))
res = mid, l = mid + 1;
else
r = mid - 1;
}
cout << res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, k;
vector < vector < int > > a;
enter(m, n, k, a);
solution(m, n, k, a);
return 0;
}
Để tiếp tục theo dõi phần của series bài viết về Mảng tổng tiền tố và Mảng hiệu, mời các bạn nhấn vào đây.
©️ Tác giả: Vũ Quế Lâm từ Viblo
All rights reserved