【一维前缀和】以及【二维前缀和的图形化理解】
目录
- 一、什么是一维前缀和？
- 1、定义：
- 2、经典例题
- 1、题目
- 2、解题思路
- 二、什么是二维前缀和
- 1、定义
- 2、初始化方式
- 3、模板题讲解
一、什么是一维前缀和？
1、定义：
一维前缀和是一种用于快速计算数组部分和的技巧。前缀和数组中的每个元素表示原数组从第一个元素到当前元素的累积和。通过预处理得到前缀和数组，可以在常数时间内计算任意区间的和。
示例：
假设有一个数组 arr = [1, 2, 3, 4, 5]，我们想快速计算某个区间 [l, r] 的和（例如，计算区间 [2, 4] 的和）。
首先构建前缀和数组 prefix，其中 prefix[i] 表示 arr[0] 到 arr[i] 的累积和：
prefix[0] = 1
prefix[1] = 1 + 2 = 3
prefix[2] = 1 + 2 + 3 = 6
prefix[3] = 1 + 2 + 3 + 4 = 10
prefix[4] = 1 + 2 + 3 + 4 + 5 = 15
所得的前缀和数组为 prefix = [0, 1, 3, 6, 10, 15]。
现在要计算区间 [2, 4]（即 arr[1] + arr[2] + arr[3]），使用前缀和可以直接计算：
prefix[4]−prefix[2-1]=15-3=12
这样，通过前缀和可以快速计算任意区间的和，而不需要逐个遍历计算。
前缀和的初始化方法（不唯一）：
public class Main {
public static void main(String[] args) {
//原数组
int[] arr={1,2,3,4,5,6};
//前缀和数组
int[] preSum=new int[arr.length];
//初始化方式
preSum[0]=arr[0];
for(int i=1;i<arr.length;i++){
preSum[i]=preSum[i-1]+arr[i];
}
}
}
2、经典例题
1、题目
蓝桥云课题目连接
2、解题思路
题目给定一个数组，数组大小表示宝石的个数，数组的元素值代表对应的价值。题目给定我们k次处理机会，每次处理只能丢弃最小价值的两个宝石（方案1）或者丢弃最大价值的一个宝石（方案2），要求最大化宝石总价值。
我们可以直接对给定的数组进行升序排序，得数组arr；计算对应已排序数组的前缀和数组preSum。那么这样做的目的是什么呢？很简单，我们可以通过arr以及preSum枚举所有可能得丢弃情况，从而选择最大化宝石总价值的丢弃方式。
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
while(t-- > 0){
// 读取宝石数量和操作次数
int n = scan.nextInt();
int k = scan.nextInt();
// 读取宝石数组
long[] arr = new long[n+1];
for(int i = 0; i < n; i++){
arr[i] = scan.nextLong();
}
// 对宝石数组进行升序排序
Arrays.sort(arr,0,n);
// 计算前缀和数组，preSum[m]表示前m个最小宝石的总和
long[] preSum = new long[n+1];
preSum[0] = 0;
for(int i = 1; i <= n; i++){
preSum[i] = preSum[i-1] + arr[i-1];
}
// 计算总和
long totalSum = preSum[n];
long ans = 0;//最终答案放到这里
long res=0;//表示使用方案2（最大价值）累计丢弃的总价值
//枚举不同丢弃情况的核心代码
for(int i = 0; i <= k; i++){//方案2，累计采用了i次
//i=0时 arr[n]=0 这是为什么arr大小定义成n的原因
res+=arr[n-i];
//preSum[2*(k-i)]模拟的是方案1（最小价值）累计丢弃的总价值
ans=Math.max(ans,totalSum-res-preSum[2*(k-i)]);
}
System.out.println(ans);
}
}
}
二、什么是二维前缀和
1、定义
定义一个4x4的二维数组arr（下标从1开始）：
arr这个二维数组对应的二维前缀和数组dp：大小也是4x4 ；dp[i][j]等于 左上角arr[1][1]到右下角arr[i][j]所有元素之和：
- 示例一：
- 示例二：
2、初始化方式
-
公式推导：
想要计算对应二维数组的前缀和也不难，用前面的状态递推即可，没错就类似动态规划。
状态表示dp[i][j]：arr[0][0]~arr[i][j]围成的矩阵的元素总合。
如图，求dp[3][3]为例：
-
细节：
有些同学可能会问如果i或者j=0，不会越界吗？这个问题非常好。我们回到刚才关于arr数组的定义上，arr这个二维数组i,j下标都是从1开始计数的，因此i或者j不可能为0，这样就可以避免越界了。具体在使用的时候，我们可以多开一行一列的数组，用来避免越界：
我们在使用二维前缀和的时候也要尤其注意这一点。
-
总结：
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j]，看起来公式很复杂，实际上理解了上图的意思，这个公式完全都不用记。
3、模板题讲解
牛客网题目链接
-
题目：
-
AC代码（java版）：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m=in.nextInt();
int n=in.nextInt();
int k=in.nextInt();
long[][] arr=new long[m+1][n+1];
long[][] dp=new long[m+1][n+1];
//读取原始数组
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
arr[i][j]=in.nextLong();
}
}
//初始化好前缀和数组，注意从1开始，避免越界
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
//直接套用刚才的公式即可
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j];
}
}
//开始循环读取两个坐标
while(k-->0){
int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();
System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
}
}
}
- AC代码（C++版）：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int m, n, k;
cin >> m >> n >> k;
// 定义原始数组和前缀和数组
vector<vector<long long>> arr(m + 1, vector<long long>(n + 1, 0));
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
// 读取原始数组，注意从1开始避免越界
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> arr[i][j];
}
}
// 初始化前缀和数组
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
//套用刚才的公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
}
}
// 开始读取多个查询
while (k-- > 0) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// 通过前缀和计算矩形区域的和
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
}
return 0;
}