前綴和

簡介

前綴和是一種用來快速求取陣列中某個區間和的技巧。概念就是讓前綴和陣列的第 $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]$ 來得到。