其實暴力加點優化就過了

但還是學一下正確的解法:前綴和

其實就跟數學上的級數很像，每一項都是前面所有項的總和

像是這樣:

原陣列 : 1 3 2 5 4

前綴和 : 1 4 6 11 15

那要怎麼做到這件事情?

迴圈跑過去加上前一項就好了 ,ex. arr[i]+=arr[i-1]

那要怎麼查詢區間和? 應該很明顯

假設要查 區間[l,r]的和

arr[l-1] 是$arr_1+arr_2+\dots +arr_{l-1}$
arr[r]是$arr_1+arr_2+\dots +arr_{l-1}+arr_l+\dots +arr_r$

下減上就會是$arr_l+\dots +arr_r$了

不過會遇到另一個問題，取餘數完大小關係喪失了，有可能a[r]還小於a[l-1]減出來是負數

問題不大，只要減完加10009再取模就好