系列文章目錄

藍橋杯系列：一維前綴和

---

---

前言

? ? 上次我介紹了一下模擬和枚舉類的題目，這次我想給大家介紹一種必會的思想，就是一維前綴和，因為假設我們要確定一個區間的和，我們每次確定一個范圍就是遍歷一次，時間復雜度有可能會很高，而我們如果構建出來前綴和數組的話就方便很多了，下面我們來看具體的：

---

?前綴和是以空間換時間

一、暴力的寫法：

? ? ? ? 先給大家來看一種暴力的寫法，這種相信大家只要思路是對的應該都可以直接寫出來。

? ? ? ? ? ?

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的時候我也會給大家更新的，接下來我會一直給大家更新藍橋杯的算法題的，大家一起加油，積極向上就完了。