目录
1.一维前缀和
原数列a：1 2 3 4 5 6 7 8 9 s[i]=a[1]+a[2]...+a[i]
前缀和数列s：1 3 6 10 15 21 28 36 45
对于求区间[L,R]的前缀和：
1.1 朴素方法（此时时间复杂度为O(n)）
int main()
{
int sum=0;
for(int i=l;i<=R;i++)
sum+=a[i];
}1.2 改进方法：
首先算好前缀和，然后利用result=s[R]-s[L-1]
#include<iostream>
using namespace std;
int n,m;//输入数列个数与查询的次数
const int N=1001;
int a[N],s[N];//定义原数列与前缀和数列
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];//求前缀和
}
while(m--)
{
int L,R;
cin>>L>>R;
cout<<s[R]-s[L-1]<<endl;//利用前缀和求出来区间内的和
}
return 0;
}2. 二维前缀和
2.1 方法
- 定义二维矩阵a
1 2 3 4
5 6 7 8-
定义其前缀和矩阵sum
我们用数组sum[i][j]表示左上角a[1][1]到左下角a[i][j]的和，其中sum[3][4]即绿色部分的和
sum[i][j]的预处理：
你要算出黄绿蓝，三个部分的和，你要知道，当你再算sum[i][j]的时候已，即
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]
1 3 6 10
6 14 24 36-
利用前缀和矩阵求a的任意子矩阵的和。我们开始来看一看一个任意的以（x1,y1）为左上角，（x2,y2）为右下角的子矩阵怎么求：
首先这个矩阵的和肯定包括在sum[x2][y2]中，但是多了一些东西，所以我们要把蓝的，黄的，绿的部分减去，首先看如何减去蓝的，用最粗暴的方法，直接减掉sum[x1-1,y2],好现在只要减掉一个绿色部分就行了，依然用简单粗暴的办法，减掉sum[x2][y1-1]，但是此时黄色被减去了两次，所以需要在加回去。因此子矩阵的和就等于sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]
2.2 代码
#include<iostream>
#include<cstring>
using namespace std;
int a[2000][2000],sum[2000][2000];
int main()
{
int n,m,q;//所给的矩阵是n*m的,有q组查询
cin >>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >>a[i][j];//输入原矩阵
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)//前缀和
for(int j=1;j<=m;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
for(int i=1;i<=q;i++)//接受查询
{
int x1,x2,y1,y2;
cin >>x1>>y1>>x2>>y2;
cout <<(sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1])<<endl;//O（1）查询
}
return 0;
} 2.3 例题
A-激光炸弹
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。
输入格式
输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示xi,yi,vi
输出格式
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
Sample Input
2 1
0 0 1
1 1 1
simple output
1
代码
#include<iostream>
using namespace std;
int s[5010][5010];//定义前缀和数组
int main()
{
int N, R;//N为目标数，R为能炸掉的正方形的边长
cin >> N >> R;
R = min(R, 5001);//地图范围一定，爆炸范围不需要很大，只需要考虑地图范围内即可
for (int i = 1; i <= N; i++)//目标的输入
{
int x, y, w;
cin >> x >> y >> w;
s[++x][++y] += w;
//x和y都可以取0，为了后面循环的方便，让他们都变到从1开始的位置
}
for (int i = 1; i <= 5001; i++)//对地图每个位置都求二维前缀和
{
for (int j = 1; j <= 5001; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
int ans = 0;
//由于在R-1或者之前的位置会消耗一部分地图外的，是没有价值的，所以从R,R开始
for (int i = R; i <= 5001; i++)
for (int j = R; j <= 5001; j++)
ans = max(ans, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
//求原来最大的与当前遍历到的RxR的正方形的所有价值总和的最大值
cout << ans;
return 0;
}
B-子矩阵求和
给出一个m * n的矩阵a，矩阵元素a[i,j]小于1000，进行q次查询，每次查询给出子矩阵的4个边界（上下左右），求该子矩阵所有元素之和。
样例中第一个查询：1 3 1 2 表示从第1行到第3行，从第1列到第2列，对应的子矩阵是：
1 2
5 6
9 10求和等于33
Input
第一行2个整数n, m，中间用空格分割，分别对应数组的行数n、列数m(1 <= m,n <= 100) 接下来n行，每行m个整数表示矩阵的内容a[i,j] 。(0 <= a[i,j] <= 1000) 接下来1行，一个数q，对应查询的数量。(1 <= q <= 1000) 接下来q行，每行4个整数，对应矩阵的上下左右边界u,d,l,r。(1 <= u <= d <= n, 1 <= l <= r <= m)
Sample Input
3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
1 3 1 2
1 2 1 3
1 3 1 3
Output
输出共q行，对应q个询问的求和结果。
Sample Output
33
24
54
代码
#include<iostream>
using namespace std;
int main()
{
int a[100][100];
int n,m;
int q;
int u, d, l, r, value, ans;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> value;
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + value;
}
}
cin >> q;
while (q--) {
cin >> u >> d >> l >> r;
ans = a[d][r] - a[d][l - 1] - a[u - 1][r] + a[u - 1][l - 1];
cout << ans << endl;
}
return 0;
}