前綴和求區間和

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)相減就會是答案。

f581 : https://test36047.wordpress.com/2023/01/11/f581-3-%e5%9c%93%e7%92%b0%e5%87%ba%e5%8f%a3/
g277 : https://test36047.wordpress.com/2023/01/18/g277-3-%e5%b9%b8%e9%81%8b%e6%95%b8%e5%ad%97/