目录

一、前缀和是什么？

一维数组

二维数组

基于 DP 计算高维前缀和

二、1387例题

题目 

代码

 运行结果

一、前缀和是什么？

一维数组

        前缀和可以简单理解为「数列的前n项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度

        例，有N个的正整数放到数组A里，现在要求一个新的数组 ，新数组的第 i 个数B[i] 是原数组A从第1个数到第 i 个数的和。则

​i=0,B[0] = A[0]，
i>1,B[i] = B[i-1] + A[i]

#include <iostream>
using namespace std;int N, A[10000], B[10000];int main() {cin >> N;for (int i = 0; i < N; i++) {cin >> A[i];}// 前缀和数组的第一项和原数组的第一项是相等的。B[0] = A[0];for (int i = 1; i < N; i++) {// 前缀和数组的第 i 项 = 原数组的 0 到 i-1 项的和 + 原数组的第 i 项。B[i] = B[i - 1] + A[i];}for (int i = 0; i < N; i++) {cout << B[i] << " ";}return 0;
}

二维数组

sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j];

基于 DP 计算高维前缀和

sum[i][state]= sum[i-1][state]+sum[i][state']
其中，state'是第i维度恰好比state少1的1点

二、1387例题

题目 

coding链接https://www.luogu.com.cn/problem/P1387 

# 最大正方形

## 题目描述

在一个 $n\\times m$ 的只包含 0  和 1 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

## 输入格式

输入文件第一行为两个整数 $n,m(1\\leq n,m\\leq 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

## 输出格式

一个整数，最大正方形的边长。

## 样例 #1

### 样例输入 #1

```
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
```

### 样例输出 #1

```
2
```

代码

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int m,n;//n行m列cin>>n>>m;int arr[n+50][m+50];int sum[n+50][m+50];/*for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>arr[i][j];//sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]}}*/for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>arr[i][j];sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];}}int ans=1;int l=2;//正方形边长，初始化从[2][2]开始，看正方形的右下角位置while(l<=min(m,n)){for(int i=l;i<=n;i++){for(int j=l;j<=m;j++){if(sum[i][j]-sum[i-l][j]-sum[i][j-l]+sum[i-l][j-l] == l*l){ans=max(ans,l);}}}l++;}cout<<ans<<endl;return 0;
}

易错点：

 运行结果