前綴和

簡介

#

前綴和是一種用來快速求取陣列中某個區間和的技巧。概念就是讓前綴和陣列的第 \(i\) 個元素儲存前 \(i\) 個元素的總和，這樣就可以在 \(O(1)\) 的時間透過兩個前綴和相減來求取區間和。

基本前綴和

#

首先，我們需要一個陣列 \(psum\) 來儲存前綴和，其中 \(psum[i]\) 儲存的是陣列 \(a\) 的前 \(i\) 個元素的總和。

接著，我們可以用以下的程式碼來建立前綴和陣列。

for (int i = 1; i <= n; i++) {
    psum[i] = psum[i - 1] + a[i];
}

最後，我們可以用以下的方法來求取陣列 \(a\) 中從第 \(l\) 個元素到第 \(r\) 個元素的區間和。

int sum = psum[r] - psum[l - 1];

這個技巧在之後的題目中會經常用到！

二維前綴和

#

如果是二維陣列，我們一樣可以透過前綴和的技巧來存取某個子矩陣的總和。

首先，我們需要一個二維陣列 \(psum\) 來儲存前綴和，其中 \(psum[i][j]\) 儲存的是二維陣列 \(a\) 的左上角 \((1, 1)\) 到右下角 \((i, j)\) 的總和。

接著，我們可以用以下的程式碼來建立二維前綴和陣列。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + a[i][j];
    }
}

也許你會好奇為上面那個算式是怎麼來的，因為根據排容原理，我們要計算的 \(psum[i][j]\)，可以透過把 \(psum[i - 1][j]\) 和 \(psum[i][j - 1]\) 加起來，再減掉 \(psum[i - 1][j - 1]\) 來得到。