前綴和$(Prefix$ $Sum)$的定義

前綴和是一種高效處理區間求和問題的算法技巧
其核心思想是通過預處理構建一個前綴和數組
使得后續的區間和查詢可以在常數時間$O(1)$內完成

核心概念

• 定義
  給定一個數組$a[\mathrm{1...}n]$,其前綴和數組$s[\mathrm{1...}n]$定義為:
  $s[0]=0(邊界條件)$
  $s[i]=a[1]+a[2]+...+a[i](前i個元素的和)$
  通過遞推計算:$s[i]=s[i?1]+a[i]$
• 作用
  快速計算區間和:查詢$a[l...r]$的和時,只需計算$s[r]?s[l?1]$,無需遍歷整個區間。
  優化時間復雜度：
  預處理:$O(n)$
  單次查詢:$O(1)$
  適用于頻繁查詢但數據不頻繁修改的場景(如靜態數組)

對比其他方法差距/使用前綴和的原因

方法	預處理時間	單次查詢時間	適用場景
暴力遍歷	O(1)	O(n)	查詢極少
前綴和	O(n)	O(1)	查詢多，數據靜態
線段樹/樹狀數組	O(n)	O(log n)	查詢和修改都頻繁

總結

前綴和通過空間換時間,將區間和查詢優化至$O(1)$,是算法競賽中的常客
若需支持動態修改,可結合差分數組或升級為樹狀數組/線段樹

前綴和代碼模板示例

#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N],s[N];
int main(){int n,q;//n=數組個數,q=詢問次數cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];//讀入初值s[i]=s[i-1]+a[i];//計算前綴和}for(int i=1;i<=q;i++){int l,r;//詢問區間cin>>l>>r;cout<<s[r]-s[l-1]<<endl;//輸出區間和}return 0;
}

原理

非常$Easy$
前綴和數組$s[x]$的值相當于$a[1]$~$a[x]$
利用這個原理計算得知
$a[l]到a[r]的和=s[r]?s[l?1]$

例題

P8218 【深進1.例1】求區間和

題目描述

給定由 $n$ 個正整數組成的序列 $a_1,a_2,?,a_n$ 和 $m$ 個區間 $[l_i,r_i]$，分別求這 $m$ 個區間的區間和。

輸入格式

第一行包含一個正整數 $n$，表示序列的長度。

第二行包含 $n$ 個正整數 $a_1,a_2,?,a_n$。

第三行包含一個正整數 $m$，表示區間的數量。

接下來 $m$ 行，每行包含兩個正整數 $l_i,r_i$，滿足 $1\le l_i\le r_i\le n$。

輸出格式

共 $m$ 行，其中第 $i$ 行包含一個正整數，表示第 $i$ 組答案的詢問。

輸入輸出樣例 #1

輸入 #1

4
4 3 2 1
2
1 4
2 3

輸出 #1

10
5

說明/提示

樣例解釋

第 $1$ 到第 $4$ 個數加起來和為 $10$。第 $2$ 個數到第 $3$ 個數加起來和為 $5$。

數據范圍

對于 $50\%$ 的數據：$n,m\le 1000$；

對于 $100\%$ 的數據：$1\le n,m\le 10^5$，$1\le a_i\le 10^4$。

分析

經典的前綴和例題
看輸入要求，輸入數組個數$n$
然后給數組$a[]$初值，再輸入詢問次數$m$
給$m$行的$l_i,r_i$并詢問$a[l_i]到a[r_i]$的區間和
跟模板一樣，但是需要把$m$的輸入改到輸入數組$a[]$的后方

$AC$代碼

#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N],s[N];
int main(){int n,m;//n=數組個數,m=詢問次數cin>>n;for(int i=1;i<=n;i++){cin>>a[i];//讀入初值s[i]=s[i-1]+a[i];//計算前綴和}cin>>m;for(int i=1;i<=m;i++){int l,r;//詢問區間cin>>l>>r;cout<<s[r]-s[l-1]<<endl;//輸出區間和}return 0;
}

題單附送

$題單$
包含前綴和、差分、離散化

~ $完結撒花$ ~

附：例題來自$洛谷$
推薦$洛谷$作為為你的刷題區域
下一篇預告：還在找~