文章目錄

• • 洛谷 B3612 求區間和
  • 洛谷 P1387 最大正方形
  • 洛谷 P3397 地毯

洛谷 B3612 求區間和

題目鏈接：洛谷 B3612 求區間和
思路： 一維前綴和的模板題。所謂前綴和，就是對原數組前i個元素求和，這個值作為新元素放在下標i的位置。
代碼如下：

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], sum[N];
int main()
{int n, m;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];sum[i] += sum[i - 1] + a[i];}cin >> m;while (m--){int l, r;cin >> l >> r;cout << sum[r] - sum[l - 1] << endl;}return 0;
}

• 時間復雜度$O(n)$
• 空間復雜度$O(n)$

洛谷 P1387 最大正方形

題目鏈接： 洛谷 P1387 最大正方形
思路： 本題有兩種方法，一種是利用二位前綴和，另一種是利用動態規劃。
代碼如下：
（前綴和）

#include <iostream>
using namespace std;
int n, m;
const int N = 105;
int a[N][N], s[N][N]; 
int ans;//保存最大邊長
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j++){cin >> a[i][j];s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];}//枚舉起點和邊長for(int i = 1; i <= n; i ++ )for(int j = 1; j <= m; j ++ )for (int l = 1; l <= min(n, m); l ++ ){int x = i + l - 1, y = j + l - 1;//正方形右下角坐標if (x > n || y > m || s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] != l * l) {break;}if (ans < l) ans = l;}cout << ans << endl;return 0;
}

• 時間復雜度$O(mnl)$
• 空間復雜度$O(n^2)$

（動態規劃）

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int a[N][N], f[N][N]; //f[i][j]表示以節點i, j為右下角，可構成的最大正方形的邊長。
int ans;
int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){cin >> a[i][j];if (a[i][j] == 1) {f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;}ans = max(ans, f[i][j]);}cout << ans << endl;return 0;
}

• 時間復雜度$O(n^2)$
• 空間復雜度$O(n^2)$

洛谷 P3397 地毯

題目鏈接： 洛谷 P3397 地毯
思路： 算是二維差分的模板題吧。所謂差分也就是前綴和的逆運算，也就是說，我們對差分數組求前綴和后得到的數組就是原數組。
代碼如下：

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int n, m;
int b[N][N], s[N][N];//b為差分數組，s為原數組（對差分數組求前綴和）int main()
{cin >> n >> m;while (m--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;b[x1][y1] += 1;b[x1][y2 + 1] -= 1;b[x2 + 1][y1] -= 1;b[x2 + 1][y2 + 1] += 1;}for(int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j++){s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];}for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= n; j ++ )cout << s[i][j] << " ";cout << endl;}return 0;
}

• 時間復雜度$O(mn+n^2)$
• 空間復雜度$O(n^2)$

---

總結： 對于前綴和、差分來說，一般比賽時不會直接作為考點，而是融合在其他類型題目中：比如利用前綴和、差分來對初始數組進行操作，從而方便我們解決問題。

最后，如果文章有錯誤，請在評論區或私信指出，讓我們共同進步！