首先我們要引入一個問題，我要求一個陣列中從頭到某一項的和要怎麼辦呢?

這邊默認第幾項都是口語上的用法，也就是首項是第 1 項

你會說簡單啊，直接遍歷陣列不就好了，這邊以加到第 end 項當例子，很輕易就可以得出

int ans = 0;
for(int i = 0 ; i < end ; i++ ){
	ans += arr[i];
}

那如果再變一下，我要求從第start項到第end項的和呢?
也不難得出

int ans = 0;
for(int i = start-1 ; i < j ; i++ ){
	ans += arr[i];
}

剛剛說了是口語化用法，要注意的是一般陣列是從索引0開始，所以是 start-1

那我們在變一下，我要進行很多次這樣的查詢，而剛剛的暴力法會導致超時也就是TLE(Time Limit Exceeded)，而優化方式就是前綴和(Prefix Sum)。

這邊要特別注意，為了避免混淆，我們在使用這一技巧(前綴和)時，可以將陣列從索引 1 開始儲存，這樣跟口語就對的上(不容易想一想結果自己打結)，而且可以避免要做額外判斷(等等會提到)

優化概念：空間換時間

我可以多用一個陣列sum[]來存算過的東西，這邊做一個定義sum[i]表示從第1項一直加到第i項的結果，這邊以 1~10 做例子

程式碼實作 (C/C++)

	int arr[11];
    int sum[11];sum[0] = 0;
    for(int i = 1 ; i < 11 ; i++) arr[i] = i;

    for(int i = 1 ; i < 11 ; i++ ){
        sum[i] = sum[i-1]+arr[i];
        printf("sum[%d] = %d\n",i,sum[i]);
    }

sum[0]我們設為0，因為根據我們對他的定義是從第1項開始，第0項就棄置不用

要做查詢就是對sum[]進行操作

	int start = 4;
    int end = 5;
    
    int ans = sum[end] - sum[start - 1];
    printf("ans = %d\n",ans);

分析

如果我們要求重複進行 Q 次查詢，每次查詢範圍是從 [start,end]。假設陣列長度是N = 10⁵，也要查10⁵次。

• 暴力法：每次查詢跑一次 for，最糟情況為Q×N=10¹⁰ ，很容易會 TLE。
• 前綴和：我們先花N的時間預處理（Preprocessing），之後每次查詢只需進行單次運算也
  就是N+Q≈2*10⁵

小整理

建立一個 prefix_sum 陣列（這邊簡寫為 S[]），其中 S[i] 代表原陣列中 **前i**項的和。

定義：

• S[0]=0
• S[i]=a₁+a₂+⋯+aᵢ

當我們要求區間 [L,R] 的和時（從第L項到第R項），公式如下：

Sum(L,R)=S[R]−S[L−1]

本篇主要集中在一維的前綴和，關於更多觀念之後也會提到

練習

1. CSES 簡單題
2. LeetCode 303

第2題就是將上面講到的概念再封裝成一個類別

開啟新部分，應該也是3篇講完，這次我先把練習題放出來了，因為概念上沒有甚麼特別的相依性。
前綴和在我個人看來是一種優化思想，而非某種特定具體的驗算法，當然或許你有甚麼不同的看法也可以提出讓我們討論討論。