Đây là bài viết số $2$ 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ố $1,$ 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ố $A$ gồm $n$ phần tử. Bạn được cho trước $k$ 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 $[l, r]$ thêm $x$ đơn vị.

Yêu cầu: In ra mảng $A$ sau khi thực hiện tất cả $k$ truy vấn?"

Input:

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.
• Dòng thứ ba chứa số nguyên dương $k$.
• Trên $k$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l, r, x$ thể hiện một truy vấn.

Ràng buộc:

• $1 \le n \le 10^5$.
• $|a_i| \le 10^9; \forall i: 1 \le i \le n$.
• $1 \le k \le 10^6$.
• $1 \le l \le r \le n$.
• $|x| \le 10^9$.

Output:

• In ra dãy $A$ sau khi thực hiện đủ $k$ 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 $O(n),$ ta sẽ xây dựng một mảng hiệu $diff(A)$ và tiến hành cập nhật trên đó trong độ phức tạp $O(1)$.

Với mảng hiệu $diff(A) \ \big(diff[i] = a_i - a_{i - 1}; \forall i: 2 \le i \le n \big);$ ta có một số trường hợp sau cho một truy vấn:

• Nếu $a_i$ và $a_{i - 1}$ không thuộc đoạn $[l, r]$ thì giá trị của hai phần tử không đổi $\to diff[i]$ không đổi.
• Nếu $a_i$ và $a_{i - 1}$ cùng thuộc đoạn $[l, r]$ thì giá trị của hai phần tử đều được cộng thêm $x \to diff[i]$ không đổi.
• Nếu chỉ một trong hai phần tử $a_i$ hoặc $a_{i - 1}$ thuộc đoạn $[l, r]$ thì một trong hai phần tử sẽ được cộng thêm $x,$ phần tử còn lại giữ nguyên $\to diff[i]$ thay đổi.

Từ đây ta thấy, mảng hiệu chỉ thay đổi khi xét tới vị trí $i$ rơi vào trường hợp cuối. Mà trường hợp cuối chỉ xảy ra khi $i = l$ hoặc $i = r + 1,$ khi đó ta sẽ tác động lên $diff[l]$ (tăng thêm $x$) và $diff[r + 1]$ (giảm đi $x$) để cập nhật đoạn. Điều này yêu cầu mảng $diff$ ban đầu phải được khai báo kích thước là $n + 2$ để không gặp lỗi truy cập mảng khi $r = n$.

Cuối cùng, ta áp dụng tính chất $A = sum(0, diff)$ để phục hồi lại mảng $A$ sau khi đã hoàn tất cập nhật.

Độ phức tạp: $O(n + k)$.

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 $A$ bất kì kích thước $m \times n$ và có các phần tử là $a_{i, j},$ trước hết ta có thêm hai định nghĩa sau:

• $diff_{hàng}(A)$: Mảng hai chiều gồm $m$ hàng, hàng thứ $i$ thể hiện mảng hiệu của hàng thứ $i$ tương ứng trên ma trận $A$.
• $diff_{cột}(A)$: Mảng hai chiều gồm $n$ cột, cột thứ $i$ thể hiện mảng hiệu của cột thứ $i$ tương ứng trên ma trận $A$.

Trên mảng một chiều, ta có tính chất: $sum\big(c, diff(A)\big) = A$ (xem lại bài viết phần $1$). Để 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 $A$ sẽ tồn tại hàng $0$ và cột $0,$ với các giá trị trên hàng và cột này đều bằng $0$. Như vậy, mảng hiệu của mảng $A$ sẽ là mảng $diff$ thỏa mãn:

$$sum(diff) = A$$

Với $sum$ ở đây là tổng tiền tố hai chiều của mảng $diff$

Gọi $diff = diff_{cột}\big(diff_{hàng}(A)\big),$ ta có:

Lúc này mảng $sum(diff)$ sẽ có giá trị như sau:

(theo công thức Bao hàm - Loại trừ)

Như vậy ta kết luận, $sum(diff) = A,$ mảng $diff$ vừa dựng chính là mảng hiệu của $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 $A$ bằng hai cách:

• Dùng trực tiếp công thức: $diff_{i, j} = a_{i, j} - a_{i, j - 1} - a_{i - 1, j} + a_{i - 1, j - 1}$.
• Tính $diff_{hàng}$ cho từng hàng của $A,$ gán vào mảng $A'$ rồi tính $diff_{cột}$ cho mảng $A'$.

Tuy nhiên, cách $1$ 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 $1$:

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 $x$ cho toàn bộ các ô nằm trong hình chữ nhật con $(r_1, c_1, r_2, c_2)$ - với $(r_1, c_1)$ là tọa độ ô trái trên, $(r_2, c_2)$ là tọa độ ô phải dưới như sau:

• Khi tính $diff_{hàng}$ cho từng hàng của $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 $c_1$) và biên phải (cột $c_2 + 1$) của bảng.
• Tiếp tục tính $diff_{cột}$ cho mảng $diff_{hàng},$ chỉ có các phần tử tại hàng $r_1$ và $r_2 + 1$ sẽ bị tác động bởi thao tác cập nhật.

Từ đây ta rút ra, chỉ có $4$ phần tử của $diff(A)$ bị tác động bởi thao tác cập nhật, đó là các tọa độ $(r_1, c_1), (r_1, c_2 + 1), (r_2 + 1, c_1)$ và $(r_2 + 1, c_2 + 1)$. Trong đó, các phần tử ở $(r_1, c_1)$ và $(r_2 + 1, c_2 + 1)$ sẽ tăng thêm một lượng $x;$ còn tại $(r_1, c_2 + 1)$ và $(r_2 + 1, c_1)$ sẽ trừ đi một lượng $x$. Như vậy mỗi thao tác cập nhật chỉ diễn ra trong $O(1)$.

Sau khi thực hiện hết cập nhật, ta phục hồi lại mảng $A$ theo công thức:

$$sum\big(diff(A)\big) = A$$

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 $diff$ là mảng hiệu ba chiều của $A,$ thì bằng phương pháp Bao hàm - Loại trừ, ta có thể dựng được mảng $diff$ 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 $[x_1, x_2] \times [y_1, y_2] \times [z_1, z_2],$ ta cần cập nhật giá trị tại $8$ 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 $A$ 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 độ $(x_1, y_1, z_1)$ được tô màu trắng. Phần tử $diff$ ứng với các đỉnh trắng được cộng thêm lượng $x;$ ngược lại, phần tử ứng với đỉnh đen thì trừ đi lượng $x$.

Truy vấn cập nhật lúc này sẽ chỉ tốn thời gian $O(1)$.

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 $A$ gồm $n$ phần tử nguyên không âm $a_1, a_2, \dots, a_n$.

Có $q$ truy vấn, mỗi truy vấn có dạng $(l,r,d),$ có nghĩa là tăng phần tử thứ $l$ lên $d$ đơn vị, phần tử thứ $l+1$ lên $2 \times d$ đơn vị, ..., phần tử thứ $r$ lên $(r-l+1) \times d$ đơn vị. Nói cách khác, phần tử thứ $i \in [l,r]$ sẽ được tăng thêm $(i-l+1) \times d$ đơn vị.

Yêu cầu: Hãy in ra dãy $a$ sau khi thực hiện đủ $q$ truy vấn?

Input:

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng thứ hai gồm $n$ số nguyên không âm miêu tả dãy $A$.
• Trên $q$ dòng sau, mỗi dòng gồm $3$ số nguyên $(l,r,d)$ miêu tả truy vấn.

Ràng buộc:

• $1 \le n,q \le 10^6$.
• $0 \le a_i,d_i \le 10^5; \forall i: 1 \le i \le n$.

Output:

• Gồm một dòng in ra $n$ số, số thứ $i$ là giá trị của phần tử $a_i$ sau khi thực hiện $q$ 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 $[l,r,d]$ ta có:

• Phần tử thứ $i \ (l \le i \le r)$ sẽ được tăng lên $(i-l+1)\times d$ đơn vị, đặt $\beta = (i-l+1)\times d \Leftrightarrow \beta = i \times d - (l-1)\times d$.

Như vậy, với mỗi phần tử $i \in [l, r]$, ta sẽ có hai pha tăng giá trị của nó lên $i\times d$ và $-(l-1)\times d$.

Pha thứ hai có thể dễ dàng dùng mảng hiệu để tính. Trong code mẫu nó là mảng $C$.

Nhưng pha tăng lên $i \times d$ đơn vị, ta cần làm như sau:

• Gọi $cnt[i]$ là số lần phần tử $i$ được cộng vào giá trị $i$.
• Dễ thấy, với mỗi thao tác $[l,r,d]$, mảng $cnt[i]$ sẽ tăng lên $d$ đơn vị từ vị trí $l$ tới $r$. 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 $B$.

Ta kết hợp cả mảng $cnt$ vào để tính giá trị mảng $A$.

Độ phức tạp: $O(n)$.

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ó $m$ hàng và $n$ cột. Các hàng của bảng được đánh số từ $1$ tới $m$ từ trên xuông dưới, các cột của bảng số được đánh số từ $1$ tới $n$ từ trái qua phải. Giá trị của số nằm ở hàng $i$ cột $j$ được kí hiệu là $a_{i, j}$. Cần thực hiện lần lượt $Q$ thao tác, thao tác thứ $t \ (1 \le t \le Q)$ được mô tả bằng bộ năm số $x_t,y_t,u_t,v_t,c_t$, thao tác này sẽ tăng tất cả các phần tử $a(i,j)$ với mọi $x_i \le i \le u_t, y_t \le j \le v_t$ lên một lượng là $c_t \ (c_t > 0)$.

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ả $Q$ 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 $Q$ 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 $Q-1$ 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 $Q$ thao tác, gọi $W_t$ là giá trị lớn nhất trong bảng sau khi bỏ đi thao tác thứ $t \ (1 \le t \le Q)$. Hãy tính $\text{min}(W_1,W_2,...,W_Q)?$

Input:

• Dòng đầu chứa hai số nguyên dương $n,m$ .
• Trên $n$ dòng tiếp theo, dòng thứ $i$ gồm $n$ số nguyên không âm $a_{i,1}, a_{i,2}, ..., a_{i,n}$.
• Dòng tiếp theo chứa số nguyên dương $Q$.
• Tiếp theo là $Q$ dòng, dòng thứ $t$ gồm năm số nguyên dương $x_t,y_t,u_t,v_t,c_t$ - thể hiện một thao tác.

Ràng buộc:

• $1 \le n \times m \le 10^6$.
• $1 \le Q \le 10^6$.
• $a_{i,j} \le 10^9; \forall i, j: 1 \le i \le m, 1 \le j \le n$.
• $c_i \le 10^3; \forall i: 1 \le i \le Q$.

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 $2D$ để tăng bảng nhanh chóng. Khi kết thúc $Q$ truy vấn ta sẽ thu được bảng mới trong $O(m \times n)$.

Sau đó, ta sẽ xét từng truy vấn, xem liệu khi xóa truy vấn này đi thì $\text{max}$ 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à $c$ (tức giá trị tăng lên là $c$). Gọi $\alpha$ là giá trị $\text{max}$ của bảng sau khi thực hiện $Q$ truy vấn.

Như vậy, giá trị $\text{max}$ khi bỏ truy vấn này đi sẽ là giá trị lớn nhất của $\alpha - w$ 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 $\text{min, max}$ tiền tố và hậu tố - áp dụng Quy hoạch động trong $O(n)$. Các bạn xem lời giải để hiểu rõ hơn!

Độ phức tạp: $O(m \times n + Q)$.

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

• VNOJ - NKSEQ
• CSES - Subarray Sums II
• CSES - Subarray Divisibility
• Codeforces - Good Subarrays

Mảng tổng tiền tố nhiều chiều

• CSES - Forest Queries
• USACO - The Lazy Cow
• USACO - Painting the Barn
• VNOJ - MAXCUB

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

• Codechef - COW3E
• WCIPEG - CAKE

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/