蓝桥杯备赛系列——倒计时50天！

蓝桥杯备赛系列

倒计时50天！

前缀和和差分

知识点

**前缀和数组：**假设原数组用a[i]表示，前缀和数组用sum[i]表示，那么sum[i]表示的是原数组前i项之和，注意一般用前缀和数组时，原数组a[i]的有效下标是从1开始的。式子如下，

s u m [ n ] = ∑ i = 1 n a [ i ] sum[n]=\sum_{i=1}^n a[i] sum[n]=i=1∑n​a[i]

**差分数组：**假设原数组用a[i]表示，差分数组用d[i]表示，那么d[i]表示的是a[i]和a[i-1]之差，注意一般用差分数组时，原数组a[i]的有效下标也是从1开始的。式子如下，

d [ n ] = a [ i ] − a [ i − 1 ] d[n]=a[i]-a[i-1] d[n]=a[i]−a[i−1]

接下来看一下前缀和和差分的模板题。

前缀和模板

题目描述

给定一个长度为 n n n的数组 a 1 , a 2 , . . . . a n . a_1,a_2,....a_n. a1​,a2​,....an​.

接下来有 q q q次查询, 每次查询有两个参数 l , r l, r l,r.

对于每个询问, 请输出 a l + a l + 1 + . . . + a r . a_l+a_{l+1}+...+a_r. al​+al+1​+...+ar​.

输入描述

第一行包含两个整数 n n n和 q q q.

第二行包含n个整数, 表示 a 1 , a 2 , . . . . a n . a_1,a_2,....a_n. a1​,a2​,....an​.

接下来q行,每行包含两个整数 l和r.

1 ≤ n , q ≤ 1 0 5 1≤n,q≤10^5 1≤n,q≤105

− 1 0 9 ≤ a [ i ] ≤ 1 0 9 −10^9≤a[i]≤10^9 −109≤a[i]≤109

1 ≤ l ≤ r ≤ n 1≤l≤r≤n 1≤l≤r≤n

输出描述

输出 q q q行,每行代表一次查询的结果.

样例输入

3 2
1 2 4
1 2
2 3

样例输出

3
6

题目分析

前缀和最经典的一个作用就是以O（1）的时间复杂度求区间和。

sum[l-1]=a[1]+a[2]+a[3]+…+a[l-1]

sum[r]=a[1]+a[2]+a[3]+…+a[l-1]+a[l]+…+a[r]

sum[r]-sum[l-1]=a[1]+a[2]+a[3]+…+a[l-1]+a[l]+…+a[r]-(a[1]+a[2]+a[3]+…+a[l-1])

​ =a[l]+a[l+1]+…+a[r]

所以区间[l,r]的和可以用sum[r]-sum[l-1]表示。

题目代码

import java.util.Scanner;
public class Main{
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int q = scanner.nextInt();
	int a[] = new int[n+1];
	long sum[] = new long[n+1];
	for(int i = 1;i 
		int l = scanner.nextInt();
		int r = scanner.nextInt();
		System.out.println(sum[r]-sum[l-1]);
	}
}
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] strings = br.readLine().split(" ");
	int n = Integer.parseInt(strings[0]);
	int m = Integer.parseInt(strings[1]);
	int q = Integer.parseInt(strings[2]);
	long a[][] = new long[n+1][m+1];
	long sum[][] = new long[n+1][m+1];
	for(int i = 1;i 
		strings = br.readLine().split(" ");
		for(int j = 1;j 
			a[i][j] = Integer.parseInt(strings[j-1]);
		}
	}
	
	for(int i = 1;i 
		for(int j = 1;j 
			sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	while(q--  0) {
		strings = br.readLine().split(" ");
		int x1 = Integer.parseInt(strings[0]);
		int y1 = Integer.parseInt(strings[1]);
		int x2 = Integer.parseInt(strings[2]);
		int y2 = Integer.parseInt(strings[3]);
		System.out.println(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]);
	}
}
}

public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int m = scanner.nextInt();
	long[] a = new long[n+1];
	long[] s = new long[n+1];
	for (int i = 1; i