蓝桥杯备赛系列——倒计时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 21 2 41 22 3

样例输出

36

题目分析

前缀和最经典的一个作用就是以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