章節2-4.常用概念(一):前綴和

前綴和

前綴和(prefix sum)，是對一個數列進行處理的方式，透過建立一個新的數列，可以大幅減少查詢原始數列中某部分總和的複雜度。
對於一個長度為n的數列a₀,a₁,...,a_n-1，我們可以建立對應的前綴和數列pre₀,pre₁,...,pre_n-1，其中pre_i的定義是從a₀累加到a_i的和，或者以比較正式的數學來表示為$pre_i=\sum_{k=0}^i a_k$，而這也正是數學中級數的概念，不過就算不知道數學上的級數也沒關係，下面只會用到最基本的數學來介紹前綴和。

當我們建立前綴和數列時，我們並不需要對於每個pre_i都重新計算一次，透過觀察前綴和的意義，可以發現對於i>0，前綴和也可以定義為pre_i=pre_i-1+a_i，換句話說就是前i項的和可以利用前i-1項的和再加上第i項得到，因此我們如果有pre_i-1的話，就可以在一次加法就完成前綴和的計算。
因此只要依序計算前綴和，我們就可以用O(1)算出每項前綴和，用O(n)計算整個前綴和數列，相較之下如果計算前綴和時只利用原始數列一直累加，最後需要O(n²)才能完整算出整個前綴和數列。

不過還有一點需要注意的是，用以上方式建立的前綴和，只要原始數列有任何一個值改變，就會使前綴和數列部分或全部失效，因此只適用在原始數列不改變的情況。如果原始數列會改變的話，仍有高效率的方式可以處理前綴和，但會需要用到章節5才介紹的資料結構，因此暫時可以先忽略這種情況。

以下為範例程式碼。

#include<bits/stdc++.h>
using namespace std;
int a[100005]; //由於可能出現原始數列a[i]在範圍[-1e9,1e9]內，可以用int處理
long long int pre[100005]; //但加起來會溢位的情況，因此記得前綴和可以開long long int來存
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    pre[0]=a[0]; //上述利用現有前綴和計算下一個前綴和只適用於i>0的情況，我們需要另外定義pre[0]
    for(int i=1;i<n;i++)pre[i]=pre[i-1]+a[i];
    //若a為「2,4,5,1,3」
    //則pre為「2,6,11,12,15」
}

#include<bits/stdc++.h>
using namespace std;
int a[100005];
long long int pre[100005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)pre[i]=( i ? pre[i-1] : 0 )+a[i]; //若i不為0等同條件成立，括號的值等同於pre[i-1]，否則括號的值為0
}

除了0-based(從0開始編號)前綴和，也很多人習慣寫1-based(從1開始編號)前綴和，雖然先前提到過建議陣列從索引0開始存值，這樣在使用內建函式如sort的時候比較方便，但在前綴和這邊不用特別考慮這件事情，因為前綴和通常不會套用到內建函式，而1-based前綴和有其優點，首先是建立時pre[0]可以固定為0，然後對於所有i都可以使用pre_i=pre_i-1+a_i來計算了，還有後續介紹的其他用途用起來也比較方便。
但建議前綴和的索引編號與原陣列的編號一致，否則請特別留意索引轉換的問題。
以下內容若沒有特別註明還是以0-based紀錄前綴和。

區間和

前綴和雖然可以用O(n)建立一個數列來儲存從開頭累加到任意位置的值，但這還不夠實用，其實我們只要有了前綴和數列，就可以透過一次減法運算得到原始數列中任意連續範圍的和，或者稱為區間和(range sum)。如果我們需要數列a在[l,r]的區間和，也就是a_l+a_l+1+...+a_r-1+a_r，其實可以透過pre_r-pre_l-1得到，如果乍看之下無法理解的話，請看以下直式減法。

 pre_r  =a₀+a₁+...+a_l-1+a_l+a_l+1+...+a_r-1+a_r
- pre_l-1=a₀+a₁+...+a_l-1
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
          a_l+a_l+1+...+a_r-1+a_r

需要注意的是，在原始數列與前綴和使用0-based紀錄時，如果要取[l,r]區間和的l=0時，直接套用以上式子會導致取用到pre_-1，而這在C++中是有機率導致程式中斷的，因此需要使用條件判斷來另外處理l為0的情況，請特別留意。而在採用1-based來紀錄時就不會遇到這種問題，因為左邊界l為1的話也只會用到pre₀，只要我們將其設為0就能得到正確結果。總之不管是0-based或1-based都是可行的，根據自己的習慣選擇即可。

稍微分析一下利用前綴和來取區間和的複雜度，假設原始數列長度為n，然後接下來要計算q次區間和。如果不使用前綴和，也就是每次都直接累加的話，最壞情況每次都要加n次，總複雜度O(nq)。而使用前綴和，雖然一開始建立前綴和數列就要O(n)，但接下來的每次區間和計算可以在O(1)完成，最終總複雜度為O(n+q)。

最大區間和

而介紹完區間和後，接著介紹一個非常相似的東西叫做最大區間和(maximum range sum)，或者更常見的稱呼是最大子數組(maximum subarray)，這種說法是先定義子數組(subarray)是在原始數列從頭尾刪除幾項或零項，但最終剩下的部分必須在原始數列中連續，如「3,5,7」、「7,9」是「1,3,5,7,9」的子數組，但「1,5」、「3,7,9」不是，而子數組也可以與原本的數組相等，因此每個數組也算是自己的子數組。在這樣的定義下，最大子數組是指一個數組的所有子數組中總和最大的，其實也就是一個數列的所有區間和中，最大的那一個。

而這個問題有兩個衍生版本，分別是允許空子數組，也就是完全沒有東西總和為0，跟不允許空子數組，當作答案的子數組長度至少為1，也就是必須要有真的一個區間。其差異是在數列全部為負時，允許空子數組的答案為0，而不允許空子數組則不是。以下先介紹允許空子數組的版本。

要解決這個問題，單單把所有區間和算出來是不夠的，因為一個長度為n的數列總共會有n*(n-1)/2個區間和，就算每個都用O(1)算出來總共也要O(n²)。這個問題的解決方法需要換個角度想，如果右界r已經固定了，要找出在右界為r的情況下，最大的區間和，考慮到區間和可以用pre_r減另一個前綴和pre_i得到，因此只要讓pre_i是最小的就好(但i必須小於等於r，若等於的情況就是得到空子數組)，所以如果此時已經有最小的pre_i就可以用O(1)求得右界固定的最大區間和。接著只要把這個做法擴展，把右界從0到n-1都考慮一次就好了，最重要的，此時還可以順便紀錄最小的前綴和，也就是上面提及需要用到的。
最終可以在O(n)複雜度求得最大區間和。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
long long int pre[100005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    pre[0]=a[0];
    for(int i=1;i<n;i++)pre[i]=pre[i-1]+a[i];

    long long int minpre=0; //minpre紀錄最小的前綴和，由於最初最小的前綴和就是什麼都不取的前綴和，故初始化為0
    long long int ans=0; //ans紀錄最終答案，也就是下面最大的pre[i]-minpre，因為允許空子數組，因此初始化為最壞答案也就是0
    for(int i=0;i<n;i++){
        minpre=min(minpre,pre[i]); //內建函式min能取出兩個同型別參數中較小的那個
        ans=max(ans,pre[i]-minpre); //內建函式max能取出兩個同型別參數中較小的那個
    }
    cout<<ans;
}

不允許空子數組的版本則如下。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
long long int pre[100005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    pre[0]=a[0];
    for(int i=1;i<n;i++)pre[i]=pre[i-1]+a[i];

    long long int minpre=0; //最小的前綴和一樣是什麼都不取的前綴和，初始化為0
    long long int ans=-1e18; //最壞答案是在全部為負時必須取一個a[i]，因此初始化要比a[i]最小值還小，這裡舉例所有a[i]都在[-1e9,1e9]的情況
    for(int i=0;i<n;i++){
        //由於不能取空子數組，因此要先更新ans再更新minpre，避免出現pre[i]=minpre結果得到空子數組
        ans=max(ans,pre[i]-minpre);
        minpre=min(minpre,pre[i]);
    }
    cout<<ans;
}

除了這個應用前綴和的方法外，還有一種Kadane演算法(Kadane's Algorithm)的做法，主要概念為貪心，有興趣的話可以打開以下補充內容。除此之外還有其他使用DP概念(在章節3介紹)等等的方法。

#include<bits/stdc++.h>
using namespace std;
long long int a[100005]; //由於以下使用內建max函式型別必須完全相同，故使用long long int儲存a[i]
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    long long int now=0,ans=0; //now為每步的即時結果，ans為最終答案，因為可以全部不取，將ans都初始化為0
    for(int i=0;i<n;i++){
        now=max(a[i],now+a[i]); //前者是放棄前面取的只取a[i]，後者是留下上一步取的再加上a[i]
        ans=max(ans,now);
    }
    cout<<ans;
}

#include<bits/stdc++.h>
using namespace std;
long long int a[100005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    long long int now=a[0],ans=a[0]; //因為不能不取，就先取a[0]來初始化now與ans
    for(int i=1;i<n;i++){ //然後從i=1開始跑
        now=max(a[i],now+a[i]); //前者是放棄前面取的只取a[i]，後者是留下上一步取的再加上a[i]
        ans=max(ans,now);
    }
    cout<<ans;
}