前綴和求區間和

2023. 1. 18 PM 03:00 by CBJ

所謂前綴和,是指對一個數列進行累加,並儲存於一個陣列中,對於一個位置k,前綴和的第k項就是數列第1項到第k項的加總,定義如下圖 (根據不同題目,定義的方式會有小差異,但觀念上是相等的)。

求得前綴和陣列後,我們可以利用它來快速求得某個區段[L,R]的區間和,方法如下 :

其原理也很明顯,假如我們想要取得數列位置5~12的區間和,那也等同於先取得1~12的區間和 = 前綴和(12),再減掉多餘的1~4的區間和 = 前綴和(4),因此若想取得L~R的區間和,只要將前綴和(R)與前綴和(L-1)相減就會是答案。