Quy hoạch động 5.5: Mảng tổng tiền tố và Mảng hiệu (phần 2)
Đây là bài viết số thuộc series bài viết về Mảng tổng tiền tố và Mảng hiệu. Để xem lại bài viết số mời các bạn nhấn vào đây.
III. Ứng dụng của mảng hiệu
1. Ứng dụng cơ bản
Bài toán cơ bản của mảng hiệu là bài toán cập nhật đoạn, được phát biểu như sau:
"Cho dãy số gồm phần tử. Bạn được cho trước truy vấn, với mỗi truy vấn yêu cầu cập nhật các giá trị có vị trí thuộc đoạn thêm đơn vị.
Yêu cầu: In ra mảng sau khi thực hiện tất cả truy vấn?"
Input:
- Dòng đầu tiên chứa số nguyên dương .
- Dòng thứ hai chứa số nguyên phân tách nhau bởi dấu cách.
- Dòng thứ ba chứa số nguyên dương .
- Trên dòng tiếp theo, mỗi dòng chứa ba số nguyên thể hiện một truy vấn.
Ràng buộc:
- .
- .
- .
- .
- .
Output:
- In ra dãy sau khi thực hiện đủ thao tác cập nhật.
Sample Input:
5
1 1 1 1 1
4
2 4 2
1 5 1
3 5 4
2 2 5
Sample Output:
2 9 8 8 6
Ý tưởng
Thay vì cộng lần lượt từng phần tử ở mỗi truy vấn với độ phức tạp ta sẽ xây dựng một mảng hiệu và tiến hành cập nhật trên đó trong độ phức tạp .
Với mảng hiệu ta có một số trường hợp sau cho một truy vấn:
- Nếu và không thuộc đoạn thì giá trị của hai phần tử không đổi không đổi.
- Nếu và cùng thuộc đoạn thì giá trị của hai phần tử đều được cộng thêm không đổi.
- Nếu chỉ một trong hai phần tử hoặc thuộc đoạn thì một trong hai phần tử sẽ được cộng thêm phần tử còn lại giữ nguyên thay đổi.
Từ đây ta thấy, mảng hiệu chỉ thay đổi khi xét tới vị trí rơi vào trường hợp cuối. Mà trường hợp cuối chỉ xảy ra khi hoặc khi đó ta sẽ tác động lên (tăng thêm ) và (giảm đi ) để cập nhật đoạn. Điều này yêu cầu mảng ban đầu phải được khai báo kích thước là để không gặp lỗi truy cập mảng khi .
Cuối cùng, ta áp dụng tính chất để phục hồi lại mảng sau khi đã hoàn tất cập nhật.
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
vector < int > build_diff_array(int n, vector < int >& a)
{
vector < int > diff(n + 2);
diff[1] = a[1];
for (int i = 2; i <= n; ++i)
diff[i] = a[i] - a[i - 1];
return diff;
}
void update(int l, int r, int x, vector < int >& diff)
{
diff[l] += x;
diff[r + 1] -= x;
}
void print_new_array(int n, vector < int >& diff, vector < int >& a)
{
for (int i = 1; i <= n; ++i)
{
diff[i] += diff[i - 1];
a[i] = diff[i];
cout << a[i] << ' ';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector < int > a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector < int > diff = build_diff_array(n, a);
int k;
cin >> k;
while (k--)
{
int l, r, x;
cin >> l >> r >> x;
update(l, r, x, diff);
}
print_new_array(n, diff, a);
return 0;
}
2. Mảng hiệu hai chiều
Ý tưởng
Với một mảng hai chiều bất kì kích thước và có các phần tử là trước hết ta có thêm hai định nghĩa sau:
- : Mảng hai chiều gồm hàng, hàng thứ thể hiện mảng hiệu của hàng thứ tương ứng trên ma trận .
- : Mảng hai chiều gồm cột, cột thứ thể hiện mảng hiệu của cột thứ tương ứng trên ma trận .
Trên mảng một chiều, ta có tính chất: (xem lại bài viết phần ). Để tính chất này cũng thỏa mãn trên mảng hai chiều, ta coi rằng mảng sẽ tồn tại hàng và cột với các giá trị trên hàng và cột này đều bằng . Như vậy, mảng hiệu của mảng sẽ là mảng thỏa mãn:
<center>
Với ở đây là tổng tiền tố hai chiều của mảng
</center>Gọi ta có:
Lúc này mảng sẽ có giá trị như sau:
<center>
(theo công thức Bao hàm - Loại trừ)
</center>Như vậy ta kết luận, mảng vừa dựng chính là mảng hiệu của .
Thông qua các lập luận trên, ta có thể dựng mảng hiệu hai chiều của bằng hai cách:
- Dùng trực tiếp công thức: .
- Tính cho từng hàng của gán vào mảng rồi tính cho mảng .
Tuy nhiên, cách sẽ đơn giản hơn rất nhiều, dưới đây là cài đặt xây dựng mảng hiệu hai chiều theo cách :
vector < vector < int > > build_2d_difference_array(int m, int n, const vector < vector < int > >& a)
{
vector < vector < int > > diff(m + 1, vector < int >(n + 1, 0));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
diff[i][j] = a[i][j] - a[i][j - 1] - a[i - 1][j] + a[i - 1][j - 1];
return diff;
}
Thao tác cập nhật trên mảng hai chiều
Với mảng hiệu hai chiều, ta dễ dàng thực hiện cập nhật tăng thêm một lượng cho toàn bộ các ô nằm trong hình chữ nhật con - với là tọa độ ô trái trên, là tọa độ ô phải dưới như sau:
- Khi tính cho từng hàng của thao tác cập nhật chỉ tác động lên giá trị của các phần tử ở biên trái (cột ) và biên phải (cột ) của bảng.
- Tiếp tục tính cho mảng chỉ có các phần tử tại hàng và sẽ bị tác động bởi thao tác cập nhật.
Từ đây ta rút ra, chỉ có phần tử của bị tác động bởi thao tác cập nhật, đó là các tọa độ và . Trong đó, các phần tử ở và sẽ tăng thêm một lượng còn tại và sẽ trừ đi một lượng . Như vậy mỗi thao tác cập nhật chỉ diễn ra trong .
Sau khi thực hiện hết cập nhật, ta phục hồi lại mảng theo công thức:
void update(const vector < vector < int > >& diff,
int r1, int c1, int r2, int c2, int x)
{
diff[r1][c1] += x;
diff[r2 + 1][c2 + 1] += x;
diff[r1][c2 + 1] -= x;
diff[r2 + 1][c1] -= x;
}
void print_new_array(const vector < vector < int > >& diff,
vector < vector < int > >& a, int m, int n)
{
vector < vector < int > > sum(m + 1, vector < int >(n + 1, 0));
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + diff[i][j];
a[i][j] = sum[i][j];
cout << a[i][j] << ' ';
}
cout << endl;
}
}
3. Mảng hiệu ba chiều (đọc thêm)
Ta cũng có thể tạo ra mảng hiệu cho mảng trong không gian ba chiều, tuy nhiên việc chứng minh khá phức tạp và cũng ít ứng dụng, do đó trong bài viết này chỉ giới thiệu mang tính chất tham khảo.
Nếu ta coi là mảng hiệu ba chiều của thì bằng phương pháp Bao hàm - Loại trừ, ta có thể dựng được mảng theo công thức dưới đây:
Bây giờ, với một 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í này đều nằm tại biên của không gian. Nếu tưởng tượng hình học, thì mảng sẽ giống như một hình lập phương chứa số, và các vị trí cần cập nhật sẽ tương ứng với các đỉnh của hình lập phương con đạ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 .
<center> </center>Truy vấn cập nhật lúc này sẽ chỉ tốn thời gian .
4. Một số bài tập minh họa
Bài toán 1: Tăng đoạn
Đề bài
Cho một dãy gồm phần tử nguyên không âm .
Có truy vấn, mỗi truy vấn có dạng có nghĩa là tăng phần tử thứ lên đơn vị, phần tử thứ lên đơn vị, ..., phần tử thứ lên đơn vị. Nói cách khác, phần tử thứ sẽ được tăng thêm đơn vị.
Yêu cầu: Hãy in ra dãy sau khi thực hiện đủ truy vấn?
Input:
- Dòng đầu tiên chứa số nguyên dương .
- Dòng thứ hai gồm số nguyên không âm miêu tả dãy .
- Trên dòng sau, mỗi dòng gồm số nguyên miêu tả truy vấn.
Ràng buộc:
- .
- .
Output:
- Gồm một dòng in ra số, số thứ là giá trị của phần tử sau khi thực hiện truy vấn.
Sample Input:
5
1 2 3 4 -5
3
5 5 10
1 5 4
2 3 -1
Sample Output:
5 9 13 20 25
Ý tưởng
Với mỗi truy vấn ta có:
- Phần tử thứ sẽ được tăng lên đơn vị, đặt .
Như vậy, với mỗi phần tử , ta sẽ có hai pha tăng giá trị của nó lên và .
Pha thứ hai có thể dễ dàng dùng mảng hiệu để tính. Trong code mẫu nó là mảng .
Nhưng pha tăng lên đơn vị, ta cần làm như sau:
- Gọi là số lần phần tử được cộng vào giá trị .
- Dễ thấy, với mỗi thao tác , mảng sẽ tăng lên đơn vị từ vị trí tới . Lúc này ta lại dùng mảng hiệu để tính. Trong code mẫu mảng hiệu được sử dụng là mảng .
Ta kết hợp cả mảng vào để tính giá trị mảng .
Độ phức tạp: .
Code mẫu
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn], b[maxn], c[maxn];
void update(int l, int r, int d)
{
b[l] += d;
b[r + 1] -= d;
c[l] += -(l - 1) * d;
c[r + 1] -= -(l - 1) * d;
}
void print_array(int n)
{
for (int i=1; i<=n; i++)
{
b[i] += b[i - 1];
c[i] += c[i - 1];
a[i] += b[i] * i + c[i];
cout << a[i] << ' ';
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
int q;
cin >> q;
while (q--)
{
int l, r, d;
cin >> l >> r >> d;
update(l, r, d);
}
print_array(n);
return 0;
}
Bài toán 2: Bỏ thao tác
Đề bài
Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:
Cho một bảng số nguyên gồm có hàng và cột. 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 số được đánh số từ tới từ trái qua phải. Giá trị của số nằm ở hàng cột được kí hiệu là . Cần thực hiện lần lượt thao tác, thao tác thứ được mô tả bằng bộ năm số , thao tác này sẽ tăng tất cả các phần tử với mọi lên một lượng là .
Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện thao tác.
Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.
Yêu cầu: Cho bảng số và dãy thao tác, gọi là giá trị lớn nhất trong bảng sau khi bỏ đi thao tác thứ . Hãy tính
Input:
- Dòng đầu chứa hai số nguyên dương .
- Trên dòng tiếp theo, dòng thứ gồm số nguyên không âm .
- Dòng tiếp theo chứa số nguyên dương .
- Tiếp theo là dòng, dòng thứ gồm năm số nguyên dương - thể hiện một thao tác.
Ràng buộc:
- .
- .
- .
- .
Output:
- Gồm một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.
Sample Input:
4 4
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
3
1 1 3 3 2
2 2 3 4 1
3 1 4 3 2
Sample Output:
3
Ý tưởng
Đầu tiên, ta sử dụng kĩ thuật mảng hiệu để tăng bảng nhanh chóng. Khi kết thúc truy vấn ta sẽ thu được bảng mới trong .
Sau đó, ta sẽ xét từng truy vấn, xem liệu khi xóa truy vấn này đi thì của bảng sẽ là bao nhiêu.
Giả sử ta xét một truy vấn có dạng là hình chữ nhật màu vàng bên dưới và truy vấn đó có trọng số là (tức giá trị tăng lên là ). Gọi là giá trị của bảng sau khi thực hiện truy vấn.
Như vậy, giá trị khi bỏ truy vấn này đi sẽ là giá trị lớn nhất của và giá trị lớn nhất trong các vùng màu xanh và đỏ bên dưới:
Phần xanh và đỏ ta có thể tính trước bằng kĩ thuật tiền tố và hậu tố - áp dụng Quy hoạch động trong . Các bạn xem lời giải để hiểu rõ hơn!
Độ phức tạp: .
Code mẫu
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1;
int n, m, k;
vector < vector < int > > a;
int pcol[maxn], prow[maxn], scol[maxn], srow[maxn];
struct Query
{
int x, y, u, v, c;
} q[maxn];
void get_max(int& a, int b)
{
if (a < b)
a = b;
}
void add(int x, int y, int u, int v, int c)
{
a[x][y] += c;
a[u + 1][y] -= c;
a[x][v + 1] -= c;
a[u + 1][v + 1] += c;
}
void solution()
{
int maxv = 0;
for (int i = 1; i <= m; ++i)
{
prow[i] = prow[i - 1];
for (int j = 1; j <= n; ++j)
{
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
get_max(maxv, a[i][j]);
get_max(prow[i], a[i][j]);
}
}
for (int j = 1; j <= n; ++j)
{
pcol[j] = pcol[j - 1];
for (int i = 1; i <= m; ++i)
get_max(pcol[j], a[i][j]);
}
for (int i = m; i >= 1; --i)
{
srow[i] = srow[i + 1];
for (int j = n; j >= 1; --j)
get_max(srow[i], a[i][j]);
}
for (int j = n; j >= 1; --j)
{
scol[j] = scol[j + 1];
for (int i = m; i >= 1; --i)
get_max(scol[j], a[i][j]);
}
int res = maxv;
for (int i = 1; i <= k; ++i)
{
int x = q[i].x, y = q[i].y, u = q[i].u, v = q[i].v;
int val = max({maxv - q[i].c, prow[x - 1], pcol[y - 1], srow[u + 1], scol[v + 1]});
res = min(res, val);
}
cout << res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
a = vector < vector < int > >(m + 1, vector < int >(n + 1));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
{
int x;
cin >> x;
add(i, j, i, j, x);
}
cin >> k;
for (int i = 1; i <= k; ++i)
{
cin >> q[i].x >> q[i].y >> q[i].u >> q[i].v >> q[i].c;
add(q[i].x, q[i].y, q[i].u, q[i].v, q[i].c);
}
solution();
return 0;
}
IV. Danh sách bài tập tự luyện
Dưới đây là một số bài tập hay, các bạn có thể sử dụng để luyện tập. Ngoài ra còn rất nhiều các bài tập liên quan tới chủ đề này ở các trang web OJ, các bạn có thể tìm thêm tại danh sách bài VNOJ - Mảng cộng dồn.
Mảng tổng tiền tố một chiều
Mảng tổng tiền tố nhiều chiều
Mảng hiệu một chiều
- Codeforces - Little Girl and Maximum Sum
- Codeforces - Greg and Array
- Codeforces Gym - 319055E (lưu ý: để xem nội dung bài tập cần tham gia nhóm tại link này)
Mảng hiệu nhiều chiều
V. Tài liệu tham khảo
- https://vnoi.info/wiki/algo/data-structures/prefix-sum-and-difference-array.md
- https://codeforces.com/blog/entry/78762
- https://www.geeksforgeeks.org/difference-array-range-update-query-o1/
- https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/
©️ Tác giả: Vũ Quế Lâm từ Viblo
All rights reserved