解題思路#
如果使用暴力判斷，時間複雜度為 \(O(n^2 \times q)\) ，不夠快。
這時，我們可以使用二維前綴和來優化這個計算，時間複雜度為 \(O(n^2)\) 預處理、 \(O(1)\) 回答每一次查詢，能在時限內通過。
更精確來說，因為我們要求一個區塊內有多少樹（*），可以將 * 的位置定義為 \(1\)（一棵樹），. 的位置定義為 \(0\)（零棵樹）。將字元改成數字以後，便可以用之前教過的方法求出前綴和。
定義陣列#
vector<string> input(n);
...
vector<vector<int>> val(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (input[i][j] == '*') {
val[i][j] = 1;
}
}
}
預處理前綴和#
vector<vector<int>> psum(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + val[i - 1][j - 1];
}
}
註：因為此程式碼的 \(val\) 二維陣列為 0-based，在處理前綴和的時候要在 \(index\) 中多扣 \(1\)。
計算#
使用二維前綴和陣列求出區塊和：
int sum = psum[y2][x2] - psum[y1 - 1][x2] - psum[y2][x1 - 1] + psum[y1 - 1][x1 - 1];
常見錯誤#
0 / 1 based#
請自己注意自己陣列定義及題目敘述的陣列 / 值是從 \(0\) 開始還是從 \(1\) 開始（通常題目都是 1-based）。
輸入順序#
此題的輸入順序並非 x1, x2, y1, y2 或是 x1, y1, x2, y2，而是 y1, x1, y2, x2。實作的時候務必要多注意！
完整程式碼#
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<string> input(n);
for (int i = 0; i < n; i++) {
cin >> input[i];
}
vector<vector<int>> val(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (input[i][j] == '*') {
val[i][j] = 1;
}
}
}
vector<vector<int>> psum(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + val[i - 1][j - 1];
}
}
for (int i = 0; i < q; i++) {
int y1, x1, y2, x2;
cin >> y1 >> x1 >> y2 >> x2;
int sum = psum[y2][x2] - psum[y1 - 1][x2] - psum[y2][x1 - 1] + psum[y1 - 1][x1 - 1];
cout << sum << "\n";
}
}
