互联网大厂笔试基础算法-前缀和（一维&二维）算法讲解
前缀和算法作为一种基础算法，在笔试面试中遇到的次数很多，不管是秋招，春招还是暑期实习，因此还是建议大家熟练掌握，学会使用前缀和算法的模版即可~
算法讲解
前缀和算法，是用来快速求解数组中某一个区间的区间和的值，如果对于每一个询问，都可以在的时间复杂度内快速求解，如果使用枚举的思想，则平均复杂度为
，远高于
的复杂度，那么前缀和是如何做到这一点的，其实是通过区间拆分+预处理的思想得到的，预处理的复杂度为
算法步骤
对于给定的一个数组，如下图所示，其中，0~8为数组的下标
那么，对于数组任意的一个区间范围，如何快速地求解它的区间和？
首先，我们可以看几个例子
的区间和为
的区间和为
我们可以预处理一个前缀和数组，其中
表示区间
的区间和，那么我们很容易得出
的递推式
根据上述式子，我们可以得到一个前缀和数组，如下图所示
我们知道，对于区间的前缀和为
，区间
的前缀和为
，则区间
的前缀和为
，具体计算方式如下：
根据(1),(2)式子作差可得：
因此，我们只需要预处理出前缀和数组，就可以根据上述计算公式，快速地计算出任意一个区间的区间和，在实际笔试或者面试中，为了减少边界情况的考虑，我们更习惯性地将数组下标设置为从1开始。
应用场景
-
一维前缀和主要是用于快速地求解某一个区间和，但是前缀和是静态的算法，就是说这个数组中每一个元素的值不能被修改，如果要一边修改一边动态查询，就需要使用树状数组或者线段树这种数据结构来实现动态查询。
-
二维前缀和主要是针对二维场景，比如对于一个矩阵，矩阵的长度为
，宽度为
，它对应有
个整数点，每一个点对应的权值不同，使用二维前缀和可以快速求出起点为
，终点为
的小矩形的权值和。
注意：本算法一般是基础算法，笔试中很少会单独考察，一般会结合哈希表，动态规划，贪心等算法考察。
算法模版
一维前缀和模版
题目描述
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l,r
对于每个询问，输出原序列中从第l个数到第r个数的和。
输入格式
第一行包含两个整数
n和m。第二行包含
n个整数，表示整数数列。接下来
m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式
共
m行，每行输出一个询问的结果。
数据范围
输入样例
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例
3
6
10
题解：前缀和模板题，大家直接把这个板子背过就行，笔试中遇到就直接套用即可
#include <iostream>
using namespace std;
const int N = 1e+6 + 10;
int a[N], S[N],n,m;
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i=1;i<=n;i++)
S[i]=S[i-1]+a[i];
while (m--)
{
int l;int r;
cin>>l>>r;
printf("%d\n",S[r]-S[l-1]);
}
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 1000005;
int[] a = new int[N];
int[] S = new int[N];
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
S[i] = S[i - 1] + a[i];
}
while (m-- > 0) {
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(S[r] - S[l - 1]);
}
sc.close();
}
}
n, m = map(int, input().split())
a = [0] * (n + 1)
S = [0] * (n + 1)
a[1:n + 1] = map(int, input().split())
for i in range(1, n + 1):
S[i] = S[i - 1] + a[i]
for _ in range(m):
l, r = map(int, input().split())
print(S[r] - S[l - 1])
二维前缀和模版
题目描述
输入一个 行
列的整数矩阵，再输入
个询问，每个询问包含四个整数
，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 。
接下来 行，每行包含
个整数，表示整数矩阵。
接下来行，每行包含四个整数
，表示一组询问。
输出格式
共 行，每行输出一个询问的结果。
数据范围
输入样例
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例
17
27
21
二维前缀和模板题，这里给大家提供多语言版本的代码模版，大家背过就行，笔试的时候直接拿出来用即可。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> a[i][j], s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
while (q -- )
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
}
return 0;
}
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int q = scan.nextInt();
int[][] a = new int[n+1][m+1];
int[][] s = new int[n+1][m+1];
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ;j <= m ; j ++ ){
a[i][j] = scan.nextInt();
}
}
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ;j <= m ; j ++ ){
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
}
while(q-->0){
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
System.out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
}
}
}
N = 1010
a = [[0]*N for _ in range(N)]
s = [[0]*N for _ in range(N)]
n,m,q = map(int,input().split())
for i in range(1,n+1):
a[i] = [0] + list(map(int,input().split())) + a[m+1:]
for i in range(1,n+1):
for j in range(1,m+1):
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
while q:
x1,y1,x2,y2 = map(int,input().split())
print(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1])
q -= 1
算法练习
大家可以使用上述模版完成两道LeetCode的练习题
一维前缀和：****************************
二维前缀和：******************************
以上内容均来自于******
#秋招##春招##笔试##大厂##面经#分享互联网大厂笔试面试经验，笔试面试常见套路和模版
