前缀和

Prefix sum

前缀和的核心思想：

初始化
相减获得前缀和

模板

// 1 维
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
    
    
// 2 维
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
S[i, j] = 第i行j列格子左上部分所有元素的和
(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维前缀和

$a_1,a_2,a_3...a_n\\S_i = a_1+a_2+a_3+...a_i$

$a+b=c$

注意下标是从1开始的，其中 $S_i$ 就是前缀和，前i项的和

$S_i = S_{i-1}+a_i \\S_0 = 0 \space 利于处理边界 \\求[l~r]的前缀和， S_r-S_{l-1} \\S_r = a_1+ a_2+...a_{l-1}+a_l+...a_r \\S_{l-1}=a_1+a_2+...+a_{l-1}$

求l到r的前缀和就是求S_r - S_l-1 , 但是一定要初始化

预处理O(n)

每次询问复杂度O(1)

模板

// 前缀和就是构造了两个数组，一个a[]  一个前缀和s[]
//从而 l - r 的前缀和  S[r]-s[l-1]
//通用引入
import java.io.*;
import java.util.*;

public class PrefixSum {
	public static void main(String[] args){
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int a[] = new int[n+1];  //
        int s[] = new int[n+1];  //下标都是1开始
        
        //0. a[i]
        for(int i=1; i<=n; i++){
            a[i] = scanner.nextInt();
        }
        //1. 前缀和初始化
		for(int i=1; i<=n; i++){
            s[i] = s[i-1] + a[i];
        }
        
        
        //2. 计算前缀和
        // m次询问
        for(int i=0; i<m; i++){
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            System.out.println(s[r]-s[l-1]);  //注意是l-1
        }

二维前缀和

二维前缀和是在一个矩阵里面

核心：

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
int ans = sum[row2][col2] - sum[row1 -1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];

前缀和的初始化

求前缀和

模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
        
        int row = Integer.parseInt(str[0]);
		int col = Integer.parseInt(str[1]);
		int n = Integer.parseInt(str[2]);
        
        // a[i]
        int[][] arr = new int[row][col];
        for(int i=0;i<row;i++){
			String[] str1 = br.readLine().split(" ");
			for(int j=0;j<col;j++)
			{
				arr[i][j]=Integer.parseInt(str1[j]);
			}
		}
        
        //1. 初始化前缀和
        int[][] sum = new int[row+1][col+1];
       	for(int i=1;i<row+1;i++){
			for(int j=1;j<col+1;j++){
				//sum[i][j] = sum[i-1][j]+sum[i][j-1]
                //            -sum[i-1][j-1]+arr[i-1][j-1];
                // 注意这里，arr是从o开始
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i-1][j-1];
			}
		}
        
        //2. 求前缀和
        //n 次询问
        for(int i=0;i<n;i++){
            String[] str2 = br.readLine().split(" ");
			int row1 = Integer.parseInt(str2[0]);
			int col1 = Integer.parseInt(str2[1]);
			
			int row2 = Integer.parseInt(str2[2]);
			int col2 = Integer.parseInt(str2[3]);
            
            int ans = sum[row2][col2] - sum[row1 -1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];
            System.out.println(ans);
        }
    }
}