一、一维前缀和
以题 303. 区域和检索 - 数组不可变 为例
题目的意思就是
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
就以这个为出发点，求一个数组给定区间内的和。
如果数组的大小比较小，那么可以直接暴力求，当数组比较大时，可以采用空间换时间的方法。
就是设定一个前缀和数组presum，presum[i]存储对应前 i 个数组的和。这样求 i 到 j 的区间和就可以用presum[j]-presum[i]来求
仅对要求本身的代码：（不是这个303题的）
#include<iostream> #include<cstdio> using namespace std; const int maxn=200+10; const int N=10; int main() { int a[maxn]; int presum[maxn]; for(int i=1;i<=N;i++) { scanf("%d",&a[i]); //presum[i]=presum[i-1]+a[i];可合写到这里 } for(int i=1;i<=N;i++) { presum[i]=presum[i-1]+a[i];//预处理前缀和 } printf("%d",presum[6]-presum[2]);//求第3个数到第6个数的区间和，注意是前6个数的和减去前2个数的和！！ return 0; }
输入1 2 3 4 5 6 7 8 9 10
输出 18
对于303这个题，代码如下：(额。。这个题针对输入数据好像没法用前缀和。。。)
class NumArray { public: vector<int> array; NumArray(vector<int> nums) { for(int i=0;i<nums.;i++) { array.push_back(nums[i]); } } int sumRange(int i, int j) { int sum=0; for(int k=i;k<=j;k++) { sum+=array[k]; } return sum; } };
二、二维数组前缀和
其实和一维的差不多，就是在求presum[i][j]时，需要这样presum[i][j]=presum[i-1][j]+presum[i][j-1]+presum[i-1][j-1]+a[i][j]
因为这个求法presum[i-1][j-1]减了两次
具体看题 轰炸区最优选取
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=58; int main() { int mp[maxn][maxn]; int presum[maxn][maxn]; memset(presum,0,sizeof(presum));//置零 int n,k; while(cin>>n>>k) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&mp[i][j]); presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+mp[i][j];//预处理前缀和 } } int sum,ans=0; for(int i=k;i<=n;i++) { for(int j=k;j<=n;j++) { sum=presum[i][j]-presum[i-k][j]-presum[i][j-k]+presum[i-k][j-k];//得到某区域的和的方法相同 ans=max(ans,sum);//取和最大的那块区域 } } cout<<ans<<endl; } return 0; }
原文：https://www.cnblogs.com/theshorekind/p/14320422.html