【蓝桥杯】一学就会的小技巧（一）：前缀和

🍏前言：

• 一学就会的小技巧（二）：差分
• 一学就会的小技巧（三）：快速幂
• 一学就会的小技巧（四）：龟速乘
• 一学就会的小技巧（五）：矩阵快速幂
• 一学就会的小技巧（六）：矩阵快速幂的应用
• 数论基础—素数筛、最大公约数、最小公倍数
• 省赛真题—K倍区间（前缀和，数学，思维）

🌴🌴Hello，大家好呀！从本篇开始会收录一些算法小技巧，它们包括前缀和、差分、快速幂…这些技巧难度不大，稍加练习就能很快掌握(¬‿¬)

☕☕让我们先从前缀和开始~

题目传送门🚀🚀🚀

🍓前缀和：

👩🏻‍🏫前缀和常常用于快速求得数组的区间和，我们不妨直接从一道例题中引入前缀和这个小技巧。

👉🏻算法训练：区间求和

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

给定一个长度为n的数列a。
随后，有q次讯问。每次讯问中，给定一个起始位置x和终止位置y，希望你求出从第x个数到第y个数的和。

输入格式

第一行包含一个整数n，表示数列的长度。
第二行包含n个不超过1000的非负整数，表示数列a。
第三行包含一个整数q，表示询问个数
随后q行，每行两个正整数x、y表示求和的起始和终止位置。

输出格式

q行，每行一个整数，对应每次求和的答案

样例输入

5
3 5 2 4 1
2
1 3
2 5

样例输出

10
12

样例说明

共有2次求和操作。
第一次求和的结果为3+5+2=10
第二次求和的结果胃5+2+4+1=12

数据规模和约定

n、q<=2000

⭐题目似乎很简单，直接暴力枚举即可，很容易写出如下代码，时间复杂度 O ( N 2 ) O(N^2) O(N2)。

Java代码：

import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] num = new int[n + 1]; for (int i = 1; i <= n; i++)     num[i] = sc.nextInt(); int q = sc.nextInt(); for (int i = 0; i < q; i++) {     int ans = 0;     int x = sc.nextInt();     int y = sc.nextInt();     for (int j = x; j <= y; j++)  ans += num[j];     System.out.println(ans); } sc.close();    }}

评测结果：

⭐用时234ms，本题的数据量最大是2000，因此没有超时，但如果数据量是 1 × 1 0 5 1 \times 10^5 1×105呢？二重循环的时间复杂度是 1 × 1 0 10 1 \times 10^{10} 1×1010，对1s内可以算 1 0 8 10^8 108次的计算机来说显然不可接收，所以还需要想办法优化一下，这就要用到前缀和这个技巧了。

🍬在处理输入时，可以使用一个额外的数组sum[n]来存储前n项和，比如下面这样：

🍬让数组的下标从1开始，num[]用来存储原数组，sum[]存储前n项和，那么想求得num[1] ~ num[3]的区间和，只需要计算sum[3] - sum[1 - 1]即可。换言之，对于每次询问x y，num[x] ~ num[y]的区间和可以用sum[y] - sum[x - 1]表示。

🍬每次询问的时间复杂度为$O(1)$，总时间复杂度为$O(N)$。

🍦前缀和代码（Java）：

import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] num = new int[n + 1]; int[] sum = new int[n + 1]; // 预处理输入，sum用来存储前n项和 for (int i = 1; i <= n; i++) {     num[i] = sc.nextInt();     sum[i] = sum[i - 1] + num[i]; } int q = sc.nextInt(); // 每次询问可以利用sum立即得到区间和 for (int i = 0; i < q; i++) {     int x = sc.nextInt();     int y= sc.nextInt();     System.out.println(sum[y] - sum[x - 1]); } sc.close();    }}

🎈评测结果：

🍬可以看到速度要比暴力枚举快了一些。

🥝力扣练习题：

👩🏻‍🏫看到这里可以尝试下LeetCode303.区域和检索，是一道前缀和的模板题。

• 需要注意本题的数组已经给定，下标要做出相应修改。

🍦AC代码（Java）：

class NumArray {    private int[] sum;    public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++)     sum[i + 1] = sum[i] + nums[i];    } public int sumRange(int left, int right) { return sum[right + 1] - sum[left];    }}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */

🎈评测结果：

🍌🍌🍌
本文介绍了第一个小技巧——前缀和，它通过预处理输入来达到快速求得数组区间和的目的~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲菜狗一枚，请大佬们多多关照~