蓝桥杯冲刺：一维前缀和

系列文章目录

蓝桥杯系列：一维前缀和

---

文章目录

• 系列文章目录
• 前言
• 一、暴力的写法：
• 二、一维前缀和的模板：
  • 具体实现：
• 三、具体例题：求和
  • 1.题目参考：
  • 2.以下是具体代码实现：
• 总结

---

前言

    上次我介绍了一下模拟和枚举类的题目，这次我想给大家介绍一种必会的思想，就是一维前缀和，因为假设我们要确定一个区间的和，我们每次确定一个范围就是遍历一次，时间复杂度有可能会很高，而我们如果构建出来前缀和数组的话就方便很多了，下面我们来看具体的：

---

 前缀和是以空间换时间

一、暴力的写法：

        先给大家来看一种暴力的写法，这种相信大家只要思路是对的应该都可以直接写出来。

           

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();      // 数组长度int q = scan.nextInt();      // 查询次数int[] arr = new int[n + 1];  // 假设数组从索引1开始存储（方便输入）// 读取数组元素（1-based）for (int i = 1; i <= n; i++) {arr[i] = scan.nextInt();}// 处理每个查询for (int j = 0; j < q; j++) {int l = scan.nextInt(); // 区间左端点int r = scan.nextInt(); // 区间右端点// 暴力累加区间和int sum = 0;for (int k = l; k <= r; k++) {sum += arr[k];}System.out.println(sum);}scan.close();}
}

   

这种方式

1. 超时风险：​ 当 n = 1e5 且 q = 1e5 时，总操作次数高达 1e10，远超程序的时间限制（通常 1秒内只能处理约 1e8 次操作）。
2. ​重复计算：​ 相同区间多次查询时，暴力法会重复计算，而前缀和只需一次预处理。

二、一维前缀和的模板：

        

       具体实现：

       

public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int t = 1;while(t>0){solve(scan);t--;}scan.close();}public static void solve(Scanner scan){int n = scan.nextInt();int q = scan.nextInt();int[] arr = new int[n+1];int[] pre = new int[n+1];arr[0] = 0;pre[0] = 0;for(int i = 1;i<=n;i++){arr[i] = scan.nextInt();pre[i] = pre[i-1]+arr[i];//将前缀和确定}  for(int j = 0;j<q;j++){int l = scan.nextInt();int r = scan.nextInt();System.out.println(pre[r]-pre[l-1]);}       }}

      这个就是创建出来了一个前缀和数组，然后开始进行赋值。   

        下面我们通过这个画像来帮大家形象的理解一下：

                 

   这个就是用画图来具体的给大家来呈现的方式。

三、具体例题：求和  

    题目参考：

 

     

这也是一道有关前缀和的题，我们分析题可以发现一些规律

    a1(a2+....+an) +a2(a3+....+an)+a3(a4+....+an)

      所以通项就是:ai(a(i+1)+.....+a(n))

这道题还有一种考点，就是要用合适的数据类型来判断，因为S的值可能会超过int类型，int类型大概范围是2*10的9次方，而long的大概范围是9*10的18次方，这个很明显会超过int范围，所以所以sum应该定义为long类型。而arr[i]*(pre[n]-pre[i])也有可能溢出，所以我们也要把arr[i]转换为long类型的，防止出错。
   

以下是具体代码实现：

    

public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n = scan.nextInt();System.out.println(sum(n,scan));scan.close();}//这也是一道有关前缀和的题，我们分析题可以发现一些规律//a1(a2+....+an) +a2(a3+....+an)+a3(a4+....+an)//所以通项就是:ai(a(i+1)+.....+a(n))public static long sum(int n,Scanner scan){int[] arr = new int[n+1];int[] pre = new int[n+1];arr[0] = 0;pre[0] = 0;                for(int i = 1;i<=n;i++){arr[i] = scan.nextInt();pre[i] = pre[i-1]+arr[i];//计算前缀和的和                     }long sum = 0;for(int i = 1;i<n;i++){sum += (long)arr[i]*(pre[n]-pre[i]);}return sum;}}

 对于一维前缀和数组来说：

时间复杂度大幅降低

• ​暴力法：每次查询需要遍历区间 [l, r]，时间复杂度为 O(n)。
• ​前缀和：预处理 O(n)，之后每次查询只需 O(1)。

---

总结

  以上就是今天要讲的内容，其实前缀和就像一个基本的组件可以作为其他算法的组件，像动态规划等等，下面我们讲dp的时候我也会给大家更新的，接下来我会一直给大家更新蓝桥杯的算法题的，大家一起加油，积极向上就完了。