Chuyên đề 9: Mảng cộng dồn 2 chiều và mảng hiệu 2 chiều trong C++ và Python: tổng hình chữ nhật con O(1), cộng vào cả hình chữ nhật, hình vuông k × k tổng lớn nhất
Lời mở đầu
Ở bài 13 em đã biết mảng cộng dồn trên dãy: tính trước $P_i = a_1 + \cdots + a_i$ thì tổng đoạn $[l, r]$ chỉ là $P_r - P_{l-1}$, và mảng hiệu giúp cộng $v$ vào cả một đoạn trong $O(1)$. Nhưng đề thi rất thích cho dữ liệu là một bảng: bản đồ độ cao, cánh đồng, tấm ảnh, sân chơi… và hỏi tổng của một hình chữ nhật con, hoặc tưới nước, phủ sóng cho cả một vùng hình chữ nhật. Đó là lúc cần nâng hai kỹ thuật ấy lên hai chiều.
Bài này dùng nhiều mảng hai chiều đánh số từ 1, nên nếu em chưa vững hãy xem lại bài 7: Mảng 2 chiều. Ý tưởng then chốt chỉ là một hình vẽ bao hàm – loại trừ: cộng hai vùng chồng nhau thì phải trừ phần chung. Mình sẽ đi thật chậm, có mô phỏng bấm từng bước cho từng công thức, và chỉ ra những chỗ lệch chỉ số hay làm mất điểm.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Bài toán tổng hình chữ nhật con
Đề bài mẫu. Cho bảng số $a$ gồm $n$ hàng, $m$ cột ($n, m \le 1000$). Có $q$ câu hỏi ($q \le 10^5$), mỗi câu cho góc trên trái $(x_1, y_1)$ và góc dưới phải $(x_2, y_2)$; hãy tính tổng các ô $a[i][j]$ với $x_1 \le i \le x_2$, $y_1 \le j \le y_2$. Trong cả bài, $x$ luôn là chỉ số hàng, $y$ là chỉ số cột, đánh số từ 1.
Cách nghĩ đầu tiên: mỗi câu hỏi dùng hai vòng for cộng hết các ô trong hình chữ nhật. Một câu hỏi lớn nhất có $10^6$ ô, $10^5$ câu hỏi là $10^{11}$ phép cộng, chạy mất vài phút trong khi giới hạn thường là 1 giây (xem lại cách ước lượng ở bài 9).
Cách nghĩ thứ hai, tận dụng bài 13: làm cộng dồn 1 chiều cho từng hàng. Khi đó tổng của hàng $i$ từ cột $y_1$ tới $y_2$ tính được trong $O(1)$, và một câu hỏi chỉ cần cộng $x_2 - x_1 + 1$ hàng, tức $O(n)$. Tốt hơn nhiều, nhưng vẫn là $10^5 \cdot 10^3 = 10^8$ phép tính, vừa sát giới hạn với C++ và chắc chắn quá chậm với Python. Ta muốn mỗi câu hỏi chỉ tốn $O(1)$, giống hệt mảng một chiều.
| Cách làm | Chuẩn bị | Mỗi câu hỏi | Tổng với $n = m = 1000$, $q = 10^5$ |
|---|---|---|---|
| Cộng trực tiếp từng ô | không | $O(n \cdot m)$ | $10^{11}$: quá chậm |
| Cộng dồn 1 chiều trên từng hàng | $O(n \cdot m)$ | $O(n)$ | $10^{8}$: sát giới hạn |
| Cộng dồn 2 chiều (bài này) | $O(n \cdot m)$ | $O(1)$ | $10^6 + 10^5$: chớp mắt |
Bảng 1. Ba cách trả lời câu hỏi tổng hình chữ nhật. Chi phí chuẩn bị chỉ trả một lần, còn chi phí mỗi câu hỏi nhân lên $q$ lần.
Ý tưởng của cộng dồn 2 chiều: tính trước một bảng $S$ cùng cỡ với $a$, trong đó
$$S[i][j] = \sum_{u=1}^{i} \sum_{v=1}^{j} a[u][v],$$
tức là tổng của hình chữ nhật có góc trên trái là ô $(1, 1)$ và góc dưới phải là ô $(i, j)$. Mọi hình chữ nhật khác sẽ được “cắt” ra từ bốn hình chữ nhật dạng này. Phần 2 trả lời câu hỏi xây $S$ thế nào cho nhanh, phần 3 trả lời câu hỏi dùng $S$ ra sao.
Phần 2Xây bảng S bằng bao hàm – loại trừ
Tính từng $S[i][j]$ bằng hai vòng lặp thì mỗi ô lại tốn $O(n \cdot m)$, cả bảng thành $O(n^2 m^2)$. Ta phải dùng lại những ô $S$ đã tính. Nhìn hình dưới: vùng $(1, 1) \to (i, j)$ gồm ô $a[i][j]$ cộng với phần còn lại, và phần còn lại được phủ bởi hai vùng quen thuộc:
- $S[i-1][j]$: các hàng phía trên (hàng $1..i-1$, cột $1..j$);
- $S[i][j-1]$: các cột bên trái (hàng $1..i$, cột $1..j-1$).
Nhưng hai vùng này chồng lên nhau ở hình chữ nhật $(1, 1) \to (i-1, j-1)$, nên cộng cả hai thì phần chung bị tính hai lần. Trừ nó đi một lần là xong:
$$S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1].$$
Hình 1. Bao hàm – loại trừ: cộng vùng xanh dương và vùng tím thì vùng đỏ bị cộng hai lần, nên trừ đi $S[i-1][j-1]$, cuối cùng cộng ô vàng $a[i][j]$.
Chỉ số từ 1 và viền 0. Với $i = 1$ thì công thức cần $S[0][j]$, với $j = 1$ cần $S[i][0]$. Ta cho hàng 0 và cột 0 của $S$ đều bằng 0 (“không có ô nào thì tổng bằng 0”). Trong C++, khai báo $S$ là mảng toàn cục thì mọi phần tử tự bằng 0; trong Python, tạo bảng $(n + 1) \times (m + 1)$ toàn số 0. Khi đó công thức đúng cho mọi ô, không cần một câu if nào. Ví dụ với bảng $4 \times 5$ dưới đây (đây cũng là dữ liệu mặc định của mô phỏng):
| a: cột 1 | 2 | 3 | 4 | 5 | S: cột 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| hàng 1 | 3 | 1 | 4 | 1 | 5 | 3 | 4 | 8 | 9 | 14 | |
| hàng 2 | 9 | 2 | 6 | 5 | 3 | 12 | 15 | 25 | 31 | 39 | |
| hàng 3 | 5 | 8 | 9 | 7 | 9 | 17 | 28 | 47 | 60 | 77 | |
| hàng 4 | 3 | 2 | 3 | 8 | 4 | 20 | 33 | 55 | 76 | 97 |
Bảng 2. Ma trận $a$ (trái) và bảng cộng dồn $S$ (phải, đã bỏ hàng 0, cột 0 toàn số 0). Chẳng hạn $S[3][3] = 9 + 25 + 28 - 15 = 47$; ô cuối $S[4][5] = 97$ là tổng cả bảng.
Em bấm Tiếp để xem từng ô của $S$ được tính từ đúng 3 ô đã có: hai ô xanh dương (được cộng) và một ô đỏ (bị trừ). Thử sửa ma trận, kể cả số âm, để tự kiểm tra:
long long S[1005][1005]; // toàn cục: hàng 0, cột 0 tự bằng 0
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
// tổng hình chữ nhật (x1, y1) -> (x2, y2)
long long sum(int x1, int y1, int x2, int y2){
return S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
}for lồng nhau trên $10^6$ ô khá chậm. Để ý $S[i][j] = S[i-1][j] + (a[i][1] + \cdots + a[i][j])$: hàng $i$ của $S$ bằng hàng $i - 1$ cộng với cộng dồn 1 chiều của hàng $i$. Code Python trong bài viết đúng như vậy bằng itertools.accumulate và zip, nhanh hơn vài lần (xem thêm chuyên đề 8: Python khi đi thi).Phần 3Truy vấn tổng hình chữ nhật trong O(1)
Cần tổng vùng $D$ có góc trên trái $(x_1, y_1)$, góc dưới phải $(x_2, y_2)$. Hình chữ nhật lớn $(1, 1) \to (x_2, y_2)$ được chia thành 4 vùng như hình dưới: $A$ là góc trên trái, $B$ là dải phía trên $D$, $C$ là dải bên trái $D$. Mỗi tổ hợp vùng đều đọc được từ bảng $S$:
Hình 2. $S[x_2][y_2]$ chứa cả 4 vùng. Bỏ dải trên ($A + B$) và dải trái ($A + C$) thì vùng $A$ bị trừ hai lần, nên cộng lại $A = S[x_1 - 1][y_1 - 1]$.
$$\text{tổng}(x_1, y_1, x_2, y_2) = S[x_2][y_2] - S[x_1 - 1][y_2] - S[x_2][y_1 - 1] + S[x_1 - 1][y_1 - 1].$$
Thử với Bảng 2, hình chữ nhật $(2, 2) \to (3, 4)$ gồm các số $2, 6, 5, 8, 9, 7$ có tổng 37. Theo công thức: $S[3][4] - S[1][4] - S[3][1] + S[1][1] = 60 - 9 - 17 + 3 = 37$. Đúng!
Mô phỏng dưới đây tô màu theo số lần mỗi ô đang được tính sau từng phép cộng, trừ. Em để ý ô đỏ (bị trừ thừa) xuất hiện ở bước thứ ba và biến mất ở bước cuối. Hãy thử cả trường hợp $x_1 = 1$ hoặc $y_1 = 1$ để thấy viền 0 làm việc:
Xem code C++ / Python: cộng dồn 2 chiều và trả lời q truy vấn tổng hình chữ nhật (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long S[1005][1005]; // S[i][j] = tổng hình chữ nhật (1, 1) -> (i, j); hàng 0, cột 0 là viền 0
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long x;
cin >> x;
S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
while(q--){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1] << "\n";
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
S = [[0] * (m + 1)] # hàng 0 là viền 0
p = 3
for i in range(1, n + 1):
row = accumulate(map(int, data[p:p + m]), initial=0) # 0, a[i][1], a[i][1] + a[i][2], ...
p += m
S.append([u + r for u, r in zip(S[i - 1], row)]) # S[i][j] = S[i-1][j] + tổng hàng i tới cột j
out = []
for _ in range(q):
x1, y1, x2, y2 = int(data[p]), int(data[p + 1]), int(data[p + 2]), int(data[p + 3])
p += 4
out.append(S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1])
print('\n'.join(map(str, out)))
main()Khung chạy tay dưới đây chạy đúng chương trình trên (bản rút gọn, có lưu $a$) với dữ liệu nhỏ. Em xem bảng $S$ được lấp dần, rồi mỗi truy vấn chỉ nhìn vào 4 ô của $S$:
Những lỗi lệch chỉ số hay gặp. Công thức ngắn nhưng chỉ cần sai một ký tự là sai cả bài, mà ví dụ trong đề thường vẫn ra đúng! Bảng dưới gom những lỗi mình gặp nhiều nhất khi chấm bài học sinh:
| Lỗi | Hậu quả | Cách tránh |
|---|---|---|
Viết S[x1][y2] thay vì S[x1-1][y2] | mất cả hàng $x_1$ của hình chữ nhật | “trừ 1” luôn đi với góc trên trái |
Đánh số từ 0 nhưng vẫn dùng x1-1 | C++ đọc S[-1] ra rác; Python S[-1] là hàng cuối, sai mà không báo lỗi | đọc vào xong cộng 1 cho cả 4 chỉ số |
Khai báo S[n][m] vừa khít | tràn mảng vì cần chỉ số $n$, $m$ (và $n + 1$, $m + 1$ ở mảng hiệu) | khai báo dư: S[1005][1005] |
Dùng int cho $S$ | $10^6$ ô, mỗi ô tới $10^9$ thì tổng tới $10^{15}$: tràn số | long long cho $S$ và kết quả |
| Đề cho hai góc bất kỳ, không theo thứ tự | có thể $x_1 > x_2$, ra số âm vô nghĩa | if(x1 > x2) swap(x1, x2); tương tự với $y$ |
| Nhầm $x$ là cột (như toạ độ trên mặt phẳng) | tính sai vùng, hoặc tràn mảng khi $n \ne m$ | đọc kỹ đề: “hàng”, “cột” hay “hoành độ”, “tung độ” |
Bảng 3. Lỗi hay gặp với cộng dồn 2 chiều. Cách thử nhanh: luôn có test hình chữ nhật chạm hàng 1, cột 1, chạm hàng $n$, cột $m$, và test bảng $1 \times 1$.
Phần 4Mảng hiệu 2 chiều: cộng v vào cả hình chữ nhật
Bài toán ngược lại: có $q$ thao tác, mỗi thao tác cộng $v$ vào mọi ô của hình chữ nhật $(x_1, y_1) \to (x_2, y_2)$. Sau tất cả các thao tác, in ra bảng. Cộng trực tiếp tốn $O(n \cdot m)$ mỗi thao tác. Ở bài 13, mảng hiệu một chiều làm việc này bằng 2 phép gán: D[l] += v; D[r + 1] -= v; rồi cộng dồn. Hai chiều thì cần 4 ô góc:
| Câu lệnh | Ý nghĩa sau khi cộng dồn |
|---|---|
D[x1][y1] += v | “bật”: mọi ô $(i, j)$ với $i \ge x_1$, $j \ge y_1$ được cộng $v$ (cả góc dưới phải vô tận) |
D[x1][y2 + 1] -= v | “tắt” phần bên phải: các ô có $j > y_2$ |
D[x2 + 1][y1] -= v | “tắt” phần phía dưới: các ô có $i > x_2$ |
D[x2 + 1][y2 + 1] += v | vùng $i > x_2$, $j > y_2$ bị tắt hai lần nên bật lại một lần (lại là bao hàm – loại trừ!) |
Bảng 4. Bốn ô góc của mảng hiệu 2 chiều. Chỉ số có thể tới $n + 1$ và $m + 1$, nên mảng $D$ phải khai báo dư.
Sau khi ghi hết các thao tác, ta cộng dồn 2 chiều mảng $D$ (đúng công thức của phần 2). Giá trị tại mỗi ô $(i, j)$ lúc đó bằng tổng các $D[u][v]$ với $u \le i$, $v \le j$: thao tác nào có góc trên trái nằm ở phía trên bên trái ô $(i, j)$ thì được tính, trừ khi ô đã vượt quá hàng $x_2$ hay cột $y_2$ của thao tác đó. Mỗi thao tác tốn $O(1)$, khôi phục tốn $O(n \cdot m)$ một lần duy nhất.
Mô phỏng dưới đây cho thấy giá trị “lan ra” thế nào. Để dễ nhìn, mình cộng dồn theo từng hàng trước rồi theo từng cột; kết quả giống hệt dùng công thức bao hàm – loại trừ cho từng ô (vì cộng dồn 2 chiều chính là cộng dồn theo hàng rồi cộng dồn theo cột):
Xem code C++ / Python: mảng hiệu 2 chiều: q lần cộng v vào hình chữ nhật rồi in bảng (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long a[1005][1005], D[1005][1005]; // D cần tới chỉ số n + 1, m + 1
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
while(q--){
int x1, y1, x2, y2;
long long v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
D[x1][y1] += v; // bật
D[x1][y2 + 1] -= v; // tắt bên phải
D[x2 + 1][y1] -= v; // tắt phía dưới
D[x2 + 1][y2 + 1] += v; // góc bị tắt hai lần -> bật lại
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
D[i][j] += D[i - 1][j] + D[i][j - 1] - D[i - 1][j - 1]; // cộng dồn 2 chiều tại chỗ
cout << a[i][j] + D[i][j] << " ";
}
cout << "\n";
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
p = 3
a = []
for i in range(n):
a.append([int(x) for x in data[p:p + m]])
p += m
D = [[0] * (m + 2) for _ in range(n + 2)] # cần tới chỉ số n + 1, m + 1
for _ in range(q):
x1, y1, x2, y2, v = (int(x) for x in data[p:p + 5])
p += 5
D[x1][y1] += v # bật
D[x1][y2 + 1] -= v # tắt bên phải
D[x2 + 1][y1] -= v # tắt phía dưới
D[x2 + 1][y2 + 1] += v # góc bị tắt hai lần -> bật lại
out = []
for i in range(1, n + 1):
# cộng dồn 2 chiều: D[i][j] = D[i-1][j] (đã cộng dồn) + tổng D[i][0..j]
D[i] = cur = [u + r for u, r in zip(D[i - 1], accumulate(D[i]))]
row = a[i - 1]
out.append(' '.join(str(row[j - 1] + cur[j]) for j in range(1, m + 1)))
print('\n'.join(out))
main()Khung chạy tay dưới đây ghi 4 ô góc cho từng thao tác rồi cộng dồn tại chỗ, in luôn giá trị từng ô:
2. Quên ô thứ tư
D[x2+1][y2+1] += v: vùng góc dưới phải sẽ bị trừ $v$ oan.3. Có thao tác xen giữa câu hỏi (“cộng xong rồi hỏi ô này bằng bao nhiêu”, rồi lại cộng tiếp): mảng hiệu chỉ hợp khi mọi thao tác cộng làm trước, mọi câu hỏi làm sau. Trộn lẫn thì cần cấu trúc dữ liệu mạnh hơn như cây Fenwick 2 chiều (bài 31).
Phần 5Các dạng bài trong đề thi
Biết hai công thức rồi, cái khó trong đề thi là nhận ra chỗ cần dùng chúng. Dưới đây là những dạng mình gặp nhiều nhất; mỗi dạng đều có một bài tập tương ứng ở cuối bài.
Dạng 1: hình vuông (hình chữ nhật) kích thước cố định có tổng lớn nhất. “Chọn mảnh đất $k \times k$ thu hoạch được nhiều nhất”, “đặt tấm ảnh $k \times k$ sao cho tổng độ sáng lớn nhất”… Duyệt mọi vị trí đặt: có $(n - k + 1)(m - k + 1)$ vị trí, mỗi vị trí tính tổng trong $O(1)$. Mẹo nhỏ: duyệt theo góc dưới phải $(i, j)$ với $i \ge k$, $j \ge k$, khi đó góc trên trái là $(i - k + 1, j - k + 1)$ và tổng là $S[i][j] - S[i-k][j] - S[i][j-k] + S[i-k][j-k]$, không cần lo chỉ số ra ngoài bảng.
Xem code C++ / Python: hình vuông k × k có tổng lớn nhất (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long S[1005][1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long x;
cin >> x;
S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
long long best = LLONG_MIN;
int bx = 0, by = 0;
for(int i = k; i <= n; i++) // (i, j) là góc DƯỚI PHẢI của hình vuông
for(int j = k; j <= m; j++){
long long s = S[i][j] - S[i - k][j] - S[i][j - k] + S[i - k][j - k];
if(s > best){ best = s; bx = i - k + 1; by = j - k + 1; } // đổi về góc trên trái
}
cout << best << "\n" << bx << " " << by;
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
S = [[0] * (m + 1)] # hàng 0 là viền 0
p = 3
for i in range(1, n + 1):
row = accumulate(map(int, data[p:p + m]), initial=0) # cộng dồn hàng i
p += m
S.append([u + r for u, r in zip(S[i - 1], row)])
best, bx, by = None, 0, 0
for i in range(k, n + 1): # (i, j) là góc DƯỚI PHẢI của hình vuông
cur, up = S[i], S[i - k]
# vals[t] = tổng hình vuông có góc dưới phải (i, t + k), tức góc trên trái (i - k + 1, t + 1)
vals = [a - b - c + d for a, b, c, d in zip(cur[k:], up[k:], cur, up)]
v = max(vals)
if best is None or v > best:
best, bx, by = v, i - k + 1, vals.index(v) + 1
print(best)
print(bx, by)
main()best phải khởi tạo bằng LLONG_MIN (hoặc bằng tổng của vị trí đầu tiên), không được khởi tạo bằng 0. Đây là lỗi “ví dụ đúng, test ẩn sai” rất phổ biến.Dạng 2: đếm hình chữ nhật thoả điều kiện khi bảng nhỏ. Bảng 0/1 cỡ $40 \times 40$, hỏi có bao nhiêu hình chữ nhật con toàn số 1. Số hình chữ nhật con là $\frac{n(n+1)}{2} \cdot \frac{m(m+1)}{2} \approx 6{,}7 \cdot 10^5$, đủ ít để duyệt hết. Với mỗi hình, nó toàn số 1 khi và chỉ khi tổng bằng diện tích: $\text{tổng} = (x_2 - x_1 + 1)(y_2 - y_1 + 1)$. Nhờ cộng dồn 2 chiều, kiểm tra mỗi hình chỉ tốn $O(1)$ thay vì $O(n \cdot m)$. Cùng ý tưởng: “toàn số 0” là tổng bằng 0, “có đúng $k$ ô đen” là tổng bằng $k$ (đếm ô đen bằng cách coi ô đen là 1, ô trắng là 0).
Dạng 3: phủ sóng, tưới nước, rải phân bón. Mỗi trạm phát sóng đặt ở ô $(x, y)$ phủ hình vuông bán kính $r$, tức các ô có $|i - x| \le r$ và $|j - y| \le r$. Hỏi bao nhiêu ô không có sóng, hay ô nào bắt được nhiều trạm nhất. Mỗi trạm là một thao tác mảng hiệu trên hình chữ nhật $(\max(1, x - r), \max(1, y - r)) \to (\min(n, x + r), \min(m, y + r))$. Chú ý phải cắt hình vuông vào trong bảng bằng max, min trước khi ghi 4 góc, nếu không sẽ ghi ra chỉ số âm.
Dạng 4: chặt nhị phân cạnh hình vuông. “Tìm hình vuông lớn nhất có tổng không vượt quá $T$” với các số không âm. Nếu có một hình vuông cạnh $k$ thoả mãn thì hình vuông cạnh $k - 1$ nằm bên trong nó cũng thoả (bớt ô đi thì tổng không tăng). Vậy tính chất “có hình vuông cạnh $k$ thoả” là đơn điệu: đúng với mọi $k$ nhỏ, sai với mọi $k$ lớn. Đó đúng là điều kiện để chặt nhị phân đáp án (bài 16): mỗi lần thử một $k$, kiểm tra bằng Dạng 1 trong $O(n \cdot m)$, tổng cộng $O(n \cdot m \log \min(n, m))$.
Dạng 5: nén hai hàng thành một dãy. Khi đề hỏi về mọi hình chữ nhật (chẳng hạn đếm số hình chữ nhật có tổng đúng bằng $T$), cố định hàng trên $x_1$ và hàng dưới $x_2$, tổng từng cột trong khoảng hàng đó tạo thành một dãy $m$ số, và bài toán trở về dãy một chiều quen thuộc của bài 13 (đếm đoạn con có tổng $T$ bằng cộng dồn và map). Độ phức tạp $O(n^2 m)$.
| Dạng | Kỹ thuật | Độ phức tạp | Bài tập |
|---|---|---|---|
| Tổng nhiều hình chữ nhật | cộng dồn 2 chiều | $O(nm + q)$ | Bài 1 |
| Hình vuông $k \times k$ tốt nhất, cửa sổ quanh mỗi ô | cộng dồn 2 chiều + duyệt vị trí | $O(nm)$ | Bài 2, 3 |
| Cộng vào nhiều hình chữ nhật, phủ sóng | mảng hiệu 2 chiều | $O(nm + q)$ | Bài 4, 5 |
| Đếm hình chữ nhật trên bảng nhỏ | duyệt 4 góc + kiểm tra $O(1)$ | $O(n^2 m^2)$ | Bài 6 |
| Hình vuông lớn nhất thoả điều kiện đơn điệu | chặt nhị phân cạnh + cộng dồn | $O(nm \log n)$ | Bài 7 |
| Đếm hình chữ nhật có tổng $T$ | cố định 2 hàng, nén thành dãy | $O(n^2 m)$ | Bài 8 |
Bảng 5. Bản đồ các dạng bài dùng cộng dồn 2 chiều và mảng hiệu 2 chiều.
- Tăng Đầu Giảm Cuối (ARRAYM) (Trung bình)
- Dấu trong đoạn (MULTI) (Trung bình)
- Đặt Trạm Phủ Sóng (MOBI – OLP 30/4 Khối 10) (Trung bình)
- Mái Che (COVER) (Khá)
- Vận Chuyển Gỗ (Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 2) (Khá)
- Ma Trận May Mắn (LUCKYSQ) (Khá)
- Hình Chữ Nhật 2 (Khó)
Bài tậpLuyện cộng dồn 2 chiều và mảng hiệu 2 chiều
Cho bảng $n \times m$ số nguyên ($1 \le n, m \le 1000$, $|a_{ij}| \le 10^9$) và $q$ câu hỏi ($q \le 10^5$). Mỗi câu hỏi gồm 4 số $x_1, y_1, x_2, y_2$ ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le m$). Với mỗi câu hỏi, in ra tổng các ô từ hàng $x_1$ tới $x_2$, cột $y_1$ tới $y_2$.
Dòng đầu: $n$, $m$, $q$. Tiếp theo là $n$ dòng của bảng, cuối cùng là $q$ dòng câu hỏi.
4 5 4
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
2 2 3 4
1 1 4 5
3 1 3 1
4 1 4 537
97
5
20📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[1005][1005]; // S[i][j] = tổng hình chữ nhật (1, 1) -> (i, j); hàng 0, cột 0 là viền 0
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long x;
cin >> x;
S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
while(q--){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1] << "\n";
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
S = [[0] * (m + 1)] # hàng 0 là viền 0
p = 3
for i in range(1, n + 1):
row = accumulate(map(int, data[p:p + m]), initial=0) # 0, a[i][1], a[i][1] + a[i][2], ...
p += m
S.append([u + r for u, r in zip(S[i - 1], row)]) # S[i][j] = S[i-1][j] + tổng hàng i tới cột j
out = []
for _ in range(q):
x1, y1, x2, y2 = int(data[p]), int(data[p + 1]), int(data[p + 2]), int(data[p + 3])
p += 4
out.append(S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1])
print('\n'.join(map(str, out)))
main()Cánh đồng là bảng $n \times m$ ($1 \le n, m \le 1000$), ô $(i, j)$ cho sản lượng $a_{ij}$ ($|a_{ij}| \le 10^9$, số âm nghĩa là phải bỏ tiền cải tạo). Cần chọn một mảnh đất hình vuông $k \times k$ ($1 \le k \le \min(n, m)$) có tổng sản lượng lớn nhất. In ra tổng đó, rồi in toạ độ góc trên trái của mảnh đất. Nếu có nhiều đáp án, chọn hàng nhỏ nhất, rồi cột nhỏ nhất.
4 5 2
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 428
3 4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
best bằng LLONG_MIN vì có thể toàn số âm.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[1005][1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long x;
cin >> x;
S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
long long best = LLONG_MIN;
int bx = 0, by = 0;
for(int i = k; i <= n; i++) // (i, j) là góc DƯỚI PHẢI của hình vuông
for(int j = k; j <= m; j++){
long long s = S[i][j] - S[i - k][j] - S[i][j - k] + S[i - k][j - k];
if(s > best){ best = s; bx = i - k + 1; by = j - k + 1; } // đổi về góc trên trái
}
cout << best << "\n" << bx << " " << by;
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
S = [[0] * (m + 1)] # hàng 0 là viền 0
p = 3
for i in range(1, n + 1):
row = accumulate(map(int, data[p:p + m]), initial=0) # cộng dồn hàng i
p += m
S.append([u + r for u, r in zip(S[i - 1], row)])
best, bx, by = None, 0, 0
for i in range(k, n + 1): # (i, j) là góc DƯỚI PHẢI của hình vuông
cur, up = S[i], S[i - k]
# vals[t] = tổng hình vuông có góc dưới phải (i, t + k), tức góc trên trái (i - k + 1, t + 1)
vals = [a - b - c + d for a, b, c, d in zip(cur[k:], up[k:], cur, up)]
v = max(vals)
if best is None or v > best:
best, bx, by = v, i - k + 1, vals.index(v) + 1
print(best)
print(bx, by)
main()Ảnh đen trắng là bảng $n \times m$ điểm ảnh ($1 \le n, m \le 500$), mỗi điểm có độ sáng từ 0 đến 255. Phép làm mờ bán kính $r$ ($0 \le r \le 1000$) thay mỗi điểm $(i, j)$ bằng phần nguyên của trung bình cộng độ sáng các điểm $(u, v)$ nằm trong ảnh với $|u - i| \le r$ và $|v - j| \le r$. In ra ảnh sau khi làm mờ.
3 4 1
10 20 30 40
50 60 70 80
90 100 110 12035 40 50 55
55 60 70 75
75 80 90 95📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
max, min. Tổng lấy bằng cộng dồn 2 chiều, số điểm là diện tích hình chữ nhật đã cắt (không phải $(2r + 1)^2$!). Mẫu: góc $(1, 1)$ chỉ có 4 điểm $10, 20, 50, 60$, trung bình 35; ô $(2, 2)$ có đủ 9 điểm, tổng 540, trung bình 60.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[505][505];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, r;
cin >> n >> m >> r;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long x;
cin >> x;
S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int x1 = max(1, i - r), y1 = max(1, j - r); // cắt cửa sổ vào trong ảnh
int x2 = min(n, i + r), y2 = min(m, j + r);
long long s = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];
long long cnt = 1LL * (x2 - x1 + 1) * (y2 - y1 + 1);
cout << s / cnt << " ";
}
cout << "\n";
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, r = int(data[0]), int(data[1]), int(data[2])
S = [[0] * (m + 1)] # hàng 0 là viền 0
p = 3
for i in range(1, n + 1):
row = accumulate(map(int, data[p:p + m]), initial=0) # cộng dồn hàng i
p += m
S.append([u + r for u, r in zip(S[i - 1], row)])
out = []
for i in range(1, n + 1):
x1, x2 = max(1, i - r), min(n, i + r) # cắt cửa sổ vào trong ảnh
A, B = S[x2], S[x1 - 1]
h = x2 - x1 + 1
row = []
for j in range(1, m + 1):
y1, y2 = max(1, j - r), min(m, j + r)
s = A[y2] - B[y2] - A[y1 - 1] + B[y1 - 1]
row.append(s // (h * (y2 - y1 + 1)))
out.append(' '.join(map(str, row)))
print('\n'.join(out))
main()Khu vườn là bảng $n \times m$ ô ($1 \le n, m \le 1000$), ban đầu mọi ô khô (lượng nước 0). Có $q$ lần tưới ($q \le 10^5$), lần tưới thứ $t$ đổ thêm $v_t$ lít ($1 \le v_t \le 10^9$) vào mọi ô của hình chữ nhật $(x_1, y_1) \to (x_2, y_2)$. Cây chỉ sống được ở ô nhận ít nhất $K$ lít ($1 \le K \le 10^{18}$). Hỏi có bao nhiêu ô cây sống được?
Dòng đầu: $n$, $m$, $q$, $K$. Tiếp theo $q$ dòng, mỗi dòng $x_1, y_1, x_2, y_2, v$.
4 5 3 5
1 1 2 3 2
2 2 4 5 3
1 4 4 4 45📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long. Mẫu, sau 3 lần tưới bảng là: hàng 1: 2 2 2 4 0; hàng 2: 2 5 5 7 3; hàng 3 và 4: 0 3 3 7 3. Có 5 ô đạt ít nhất 5 lít.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long D[1005][1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
long long K;
cin >> n >> m >> q >> K;
while(q--){
int x1, y1, x2, y2;
long long v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
D[x1][y1] += v;
D[x1][y2 + 1] -= v;
D[x2 + 1][y1] -= v;
D[x2 + 1][y2 + 1] += v;
}
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
D[i][j] += D[i - 1][j] + D[i][j - 1] - D[i - 1][j - 1];
if(D[i][j] >= K) cnt++;
}
cout << cnt;
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, q, K = int(data[0]), int(data[1]), int(data[2]), int(data[3])
D = [[0] * (m + 2) for _ in range(n + 2)]
p = 4
for _ in range(q):
x1, y1, x2, y2, v = (int(x) for x in data[p:p + 5])
p += 5
D[x1][y1] += v
D[x1][y2 + 1] -= v
D[x2 + 1][y1] -= v
D[x2 + 1][y2 + 1] += v
cnt = 0
for i in range(1, n + 1):
D[i] = cur = [u + r for u, r in zip(D[i - 1], accumulate(D[i]))] # cộng dồn 2 chiều
cnt += sum(x >= K for x in cur[1:m + 1])
print(cnt)
main()Một vùng đất được chia thành bảng $n \times m$ ô ($1 \le n, m \le 1000$). Có $k$ trạm phát sóng ($k \le 10^5$), trạm thứ $t$ đặt ở ô $(x_t, y_t)$ với bán kính $r_t$ ($0 \le r_t \le 2000$) phủ sóng mọi ô $(i, j)$ trong bảng có $|i - x_t| \le r_t$ và $|j - y_t| \le r_t$. In ra hai số: số ô không có sóng, và số trạm lớn nhất cùng phủ lên một ô.
5 6 2
2 2 1
3 4 114
2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int D[1005][1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
while(k--){
int x, y, r;
cin >> x >> y >> r;
int x1 = max(1, x - r), y1 = max(1, y - r); // cắt vào trong bảng
int x2 = min(n, x + r), y2 = min(m, y + r);
D[x1][y1]++;
D[x1][y2 + 1]--;
D[x2 + 1][y1]--;
D[x2 + 1][y2 + 1]++;
}
int none = 0, best = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
D[i][j] += D[i - 1][j] + D[i][j - 1] - D[i - 1][j - 1];
if(D[i][j] == 0) none++;
best = max(best, D[i][j]);
}
cout << none << "\n" << best;
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
D = [[0] * (m + 2) for _ in range(n + 2)]
p = 3
for _ in range(k):
x, y, r = int(data[p]), int(data[p + 1]), int(data[p + 2])
p += 3
x1, y1 = max(1, x - r), max(1, y - r) # cắt vào trong bảng
x2, y2 = min(n, x + r), min(m, y + r)
D[x1][y1] += 1
D[x1][y2 + 1] -= 1
D[x2 + 1][y1] -= 1
D[x2 + 1][y2 + 1] += 1
none = best = 0
for i in range(1, n + 1):
D[i] = cur = [u + r for u, r in zip(D[i - 1], accumulate(D[i]))] # cộng dồn 2 chiều
row = cur[1:m + 1]
none += row.count(0)
best = max(best, max(row))
print(none)
print(best)
main()Cho bảng $n \times m$ ($1 \le n, m \le 40$) chỉ gồm chữ số 0 và 1, mỗi hàng là một xâu viết liền. Đếm số hình chữ nhật con (các cạnh song song với cạnh bảng, gồm ít nhất một ô) mà mọi ô đều là 1.
3 4
1101
1111
011132📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int S[45][45];
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
string s;
cin >> s;
for(int j = 1; j <= m; j++)
S[i][j] = (s[j - 1] - '0') + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
long long cnt = 0;
for(int x1 = 1; x1 <= n; x1++)
for(int x2 = x1; x2 <= n; x2++)
for(int y1 = 1; y1 <= m; y1++)
for(int y2 = y1; y2 <= m; y2++){
int s = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];
if(s != (x2 - x1 + 1) * (y2 - y1 + 1)) break; // có số 0: rộng hơn cũng hỏng
cnt++;
}
cout << cnt;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
S = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
s = data[1 + i]
up, cur = S[i - 1], S[i]
for j in range(1, m + 1):
cur[j] = (s[j - 1] == '1') + up[j] + cur[j - 1] - up[j - 1]
cnt = 0
for x1 in range(1, n + 1):
B = S[x1 - 1]
for x2 in range(x1, n + 1):
A, h = S[x2], x2 - x1 + 1
for y1 in range(1, m + 1):
for y2 in range(y1, m + 1):
if A[y2] - B[y2] - A[y1 - 1] + B[y1 - 1] != h * (y2 - y1 + 1):
break # có số 0: rộng hơn cũng hỏng
cnt += 1
print(cnt)
main()Cho bảng $n \times m$ số nguyên không âm ($1 \le n, m \le 300$, $0 \le a_{ij} \le 10^9$) và số $T$ ($0 \le T \le 10^{18}$). Tìm cạnh $k$ lớn nhất sao cho có ít nhất một hình vuông con $k \times k$ có tổng không vượt quá $T$. Nếu mọi ô đều lớn hơn $T$ thì in 0.
4 5 40
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 42📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long T, S[305][305];
bool ok(int k){ // có hình vuông k x k tổng <= T không?
if(k == 0) return true;
for(int i = k; i <= n; i++)
for(int j = k; j <= m; j++)
if(S[i][j] - S[i - k][j] - S[i][j - k] + S[i - k][j - k] <= T) return true;
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> T;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long x;
cin >> x;
S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
}
int lo = 0, hi = min(n, m); // ok(lo) luôn đúng
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(ok(mid)) lo = mid;
else hi = mid - 1;
}
cout << lo;
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n, m, T = int(data[0]), int(data[1]), int(data[2])
S = [[0] * (m + 1)] # hàng 0 là viền 0
p = 3
for i in range(1, n + 1):
row = accumulate(map(int, data[p:p + m]), initial=0) # cộng dồn hàng i
p += m
S.append([u + r for u, r in zip(S[i - 1], row)])
def ok(k): # có hình vuông k x k tổng <= T không?
if k == 0:
return True
for i in range(k, n + 1):
A, B = S[i], S[i - k]
for j in range(k, m + 1):
if A[j] - B[j] - A[j - k] + B[j - k] <= T:
return True
return False
lo, hi = 0, min(n, m) # ok(lo) luôn đúng
while lo < hi:
mid = (lo + hi + 1) // 2
if ok(mid):
lo = mid
else:
hi = mid - 1
print(lo)
main()Cho bảng $n \times m$ số nguyên ($1 \le n, m \le 100$, $|a_{ij}| \le 1000$, có thể âm) và số $T$ ($|T| \le 10^7$). Đếm số hình chữ nhật con có tổng đúng bằng $T$.
2 3 3
1 2 0
2 1 37📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
map (dict). Tổng $O(n^2 m \log m)$. Mẫu có 7 hình: $[1\ 2]$, $[1\ 2\ 0]$, $[2\ 1]$ ở hàng 2, ô $3$, và ba cột $1 + 2$, $2 + 1$, $0 + 3$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int a[105][105];
long long c[105];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
long long T;
cin >> n >> m >> T;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
long long ans = 0;
for(int x1 = 1; x1 <= n; x1++){
for(int j = 1; j <= m; j++) c[j] = 0;
for(int x2 = x1; x2 <= n; x2++){
for(int j = 1; j <= m; j++) c[j] += a[x2][j]; // c[j] = tổng cột j từ hàng x1 tới x2
map<long long, int> cnt; // đếm tiền tố của dãy c
cnt[0] = 1;
long long P = 0;
for(int j = 1; j <= m; j++){
P += c[j];
auto it = cnt.find(P - T);
if(it != cnt.end()) ans += it->second;
cnt[P]++;
}
}
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, T = int(data[0]), int(data[1]), int(data[2])
a = [[int(x) for x in data[3 + i * m: 3 + (i + 1) * m]] for i in range(n)]
ans = 0
for x1 in range(n):
c = [0] * m
for x2 in range(x1, n):
row = a[x2]
for j in range(m):
c[j] += row[j] # c[j] = tổng cột j từ hàng x1 tới x2
cnt = {0: 1} # đếm tiền tố của dãy c
P = 0
for x in c:
P += x
ans += cnt.get(P - T, 0)
cnt[P] = cnt.get(P, 0) + 1
print(ans)
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét