算法（蓝桥杯）-前缀和以及二维前缀和

蓝桥杯算法--前缀和以及二维前缀和

B站视频链接：A08 前缀和 二维前缀和_哔哩哔哩_bilibili

1、题目链接：【深进1.例1】求区间和 - 洛谷

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int a[N],s[N];
int n,m;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	scanf("%d",&m);
	
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]+a[i];//预处理求前缀和，类比数列求和
	}
	
	while(m--){
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);//求区间[l,r]的和
	}
	
	
	return 0;
}

2、题目链接：[HNOI2003] 激光炸弹 - 洛谷

#include <bits/stdc++.h>
using namespace std;

const int N=5005;
int n,m; //n个目标, 边长为m的正方形
int s[N][N]; //价值前缀和

int main(){
  cin>>n>>m; for(int i=0;i<n;i++){
    int x,y,v; 
    cin>>x>>y>>v;
    x++,y++; //坐标偏移，x,y均从1开始 
    s[x][y]+=v;
  }
  
  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];//简洁版，省略a[i][j]; 
  		}//预处理二维前缀和 
	}
  int res=0;
  for(int i=m; i<=5001; i++){
    for(int j=m; j<=5001; j++){
      res=max(res,s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m]);
  	}//枚举所有区间并求其和，求出最大价值 
  }
  cout<<res;
}

3、子矩阵的和

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];//初始化 
        }

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//子矩阵求和
    }

    return 0;
}