# 前綴和

## 一維前綴和

## 二維前綴和
### 說明
這是一個二維陣列，我們叫它arr[](https://)

假設我們要的二維前綴和陣列叫sum
今天，我們想要求整個藍色區域的合，如下圖：<br/>
 <br/>

但為了方便處理，我們只能透過 「長方形」來組合
我們設原點 \[1]\[1]，會這樣設而不是用 \[0]\[0] 是因為後面會用到 i - 1 及 j - 1，
我們想避免出現 \[-1]\[-1] 這樣的東西
這些要加總起來的範圍即 \[1]\[1] 到該位置所圍成的長方形，因此:<br/>

黃色部分標示的範圍代表從 \[1]\[1] (數值為 1)
加總到 \[3]\[4] (數值為 8 )的總和，也就是 sum\[3]\[4]；<br/>

綠色部分標示的範圍代表從 \[1]\[1] (數值為 1 )
加總到 \[4]\[4] (數值為 2 )的總和，也就是 sum\[4]\[4]；<br/>

紅色部分標示的範圍代表從 \[1]\[1] (數值為 1)
加總到 \[3]\[5] (數值為 ６ )的總和，也就是 sum\[3]\[5];<br/>

而紫色部分的 3 則是我們目前讀取到的值(位置: \[4]\[5] )<br/>

回到問題，假設我今天讀取到\[4]\[5],
也就是我現在要求\[1]\[1]到\[4]\[5]的總和，也就是sum\[4]\[5]，應該怎麼做呢？
在讀取到這個值之前，你想必已經做好前面的合了！<br/>

因此，圖上除了藍色部分都是已知
我們可以發現，
藍色＝（紅色＋綠色－黃色）＋紫色
sum[4][5]＝sum[3][5] +sum[4][4] +sum[3][4] +arr[4][5]
==sum[i][j]＝sum[i - 1][j]+sum[i][j - 1]+sum[i - 1][j - 1]+arr[i][j]== <br/>

:::warning
註:
如果在實作上遇到Compile Error，很有可能是因為當ｉ= 1 或ｊ= 1 時，
\[i - 1]或\[j - 1]的值並沒有事先被加入
函式\<cstring>中有memset可以幫助我們將一段記憶體區塊全部設定為某個值，
用法可參考 [C/C++ memset 用法與範例](https://shengyu7697.github.io/cpp-memset/)
:::

### 題目
１．[橄欖樹](http://fscs.fssh.khc.edu.tw:7122/problem/Dy008) (此題題解 : [FOJ題解](https://swamp-oval-2df.notion.site/6e8f1641ffc947d8b034e93a72515870)，Source:Dreamyee)