1.4 前綴和與差分
本次主要介紹前綴和房铭、差分算法驻龟，前綴和與差分互為逆運(yùn)算，是一種非常重要的算法思想缸匪。其中前綴和算法適用于需要頻繁求出一段區(qū)間和的情況翁狐，差分算法適用于將某段區(qū)間的元素全部加上一個(gè)數(shù)的情況。為了操作統(tǒng)一性和簡(jiǎn)潔性豪嗽，將前綴和數(shù)組和差分?jǐn)?shù)組都初始化0谴蔑，僅考慮插入元素操作，這樣就可以只考慮更新龟梦，而不用考慮構(gòu)造和初始化隐锭。
1.4.1 前綴和
前綴和主要是一種思想，適用于需要快速求出一段區(qū)間數(shù)字和的情況
將數(shù)組轉(zhuǎn)換為前綴和數(shù)組之后计贰，即可將快速求區(qū)間和的算法時(shí)間復(fù)雜度從
變成
初始化為了更好處理邊界
一般步驟：
- 求前綴和
- 算部分和（子矩陣的和）
前綴和.png
前綴和1.png
1.4.2 差分
- 差分和前綴和互為逆運(yùn)算
- 適用情景：操作：需要數(shù)組
在一個(gè)區(qū)間[l, r]使得該區(qū)間內(nèi)所有數(shù)全部加上c钦睡。 (在該種操作很多的情境下，差分思想起到作用)
- 為了統(tǒng)一操作躁倒，可以假設(shè)原數(shù)組
都為0荞怒，每添加一個(gè)數(shù)洒琢，都在差分?jǐn)?shù)組
上進(jìn)行一次操作（這樣可以只考慮更新，不考慮構(gòu)造褐桌、初始化）
差分1.png
差分2維.png
