在枚舉中，我們已經看過了這道例題：

我們的作法中，需要用到「快速計算某個區間的總和」這件事，當時我們就已經提到過前綴和了。這裡複習一下，當我們想要計算一個序列 $[a_1,a_2,\dots,a_N]$ 的一個區間總和 $a_l+a_{l+1}+\dots+a_r$ 時，等同於要計算

\[
\begin{array}{rl}
& (\color{blue}{a_1 + a_2 + \cdots + a_{l-1}} + \color{red}{a_l + a_{l + 1} + \cdots + a_r}) \\
-& (\color{blue}{a_1 + a_2 + \cdots + a_{l-1}}) \\ \hline
=& \phantom{(a_1 + a_2 + \cdots + a_{l-1} +}\ \ \color{red}{a_l + a_{l + 1} + \cdots + a_r}
\end{array}
\]

在補上 $a_1+a_2+\dots+a_{l-1}$ 之後，就會發現我們需要的東西都是長成 $a_1+a_2+\cdots$ 的形式，也就是一段前綴的總和，因此只要我們事先算出所有的
\[s_i=\sum_{k=1}^i s_k=a_1+a_2+\dots+a_i, \quad s_0=0\]
之後每次我們想知道 $a_l+a_{l+1}+\dots+a_r$ 是多少，就只要算 $s_r-s_{l-1}$ 就可以馬上得到了。這樣只需要花上 $O(N)$ 的預處理時間，之後每次的這種詢問都可以在 $O(1)$ 時間內回答。

我們把 $[s_0,s_1,\dots,s_N]$ 這個序列稱作 $[a_1,a_2,\dots,a_N]$ 的前綴和序列，通常會直接簡稱前綴和。注意到這裡我們的序列 $a$ 下標都是從 1 開始寫的，而 $s$ 多一個元素 $s_0$，這樣在詢問的區間本身是一個前綴時（$l=1$ 時），也可以直接寫 $s_r-s_{l-1}$，如果寫程式時也都使用從 1 開始的 index，就不用擔心使用前綴和的陣列時會戳出陣列範圍。

用前綴和計算區間和的核心精神是，當我們想知道的東西可能會長得奇形怪狀，就把它稍微變個形狀，讓我們可以用一些形式更為統一、更容易計算的東西來湊出我們想要的答案。套用到區間和上，這個「奇形怪狀的東西」就是「一個區間的總和」（有 $O(N^2)$ 種，感覺就很難算），而「形式更為統一」的東西就是前綴的總和（只有 $O(N)$ 種，超級好算），用兩個前綴的總和相減，就可以拼湊出我們想要的區間總和。

這種想法不只可以用在總和，只要是像加法這種「有辦法扣回去」的運算，就可以用一樣的方法算出區間的答案。像是假設我們改成要算區間乘法 $a_l \times \dots \times a_r$，能把乘法「扣回去」的操作當然就是除法了，因此只要先算好 $s_i=a_1 \times \dots \times a_i$，答案就是 $\frac{a_r}{a_{l-1}}$ 了，不過要小心一下序列裡有 0 時會不能這樣做。

不過，有些操作是不能「扣回去」的，就像乘以 0 的操作是不能反悔的，另一個例子是，如果今天要算的是「區間裡面數字的最大值」，取最大值這個操作是不能「扣掉」的，這種操作就不能這樣做了。

那麼這些奇形怪狀的東西還能不能是其他奇怪的形狀呢？當然可以，有時候我們也會想知道一個二維表格上，某個矩形範圍的格子數字總和是多少。

假設我們想要的是紅色範圍的數字總和，那麼可以這樣算出來：

注意黃色的部分會被扣到兩次，所以最後要加回去。這樣一來我們就把所有需要的東西變成「左上角在 $(1,1)$ 的矩形範圍總和」，假設 $s_{x,y}$ 是左上角在 $(1,1)$、右下角在 $(x,y)$ 的範圍總和，那麼我們要的答案就是
\[ s_{x_2,y_2}-s_{x_2,y_1-1}-s_{x_1-1,y_2}+s_{x_1-1,y_1-1} \]
如此一來，先花 $O(n^2)$ 的時間算出所有的 $s_{x,y}$ 後，就可以 $O(1)$ 時間回答一個矩形範圍的和了。

先看一道例題：

簡單來說，就是每個位子的機器會有各自需要產生的資料量，如果在位置 $i$ 的機器是 $p_i$、需要產生 $d_i$ 單位的資料，那答案就是 $\sum_{i=1}^n t[p_i] \times d_i$。很直覺地，要是我們知道全部 $d_i$，那越快的機器放在需要生產越多的資料當然越好，因此把 $t[i]$ 小到大排序、$d_i$ 大到小排序，然後兩兩相乘再加總就是答案。問題在於，題目並沒有直接告訴我們 $d_i$ 是多少，我們可以這樣描述我們需要解決的問題：一開始所有的 $d_i$ 都是 0，每個工作的意思是把 $d_{l[i]}$ 到 $d_{r[i]}$ 都加上 $w[i]$，我們最後需要知道所有 $d_i$ 是多少。

這樣一來就變成一個我們要講的經典問題：

剛剛那題的符號比較複雜，所以我們接下來都使用上面這個框框裡用的符號。

這乍聽之下有點困難，我們先來做一件看似無關的事。考慮一個序列 $b_1,b_2,\dots,b_N$，和它的前綴和 $s_0,s_1,\dots,s_N$，要是我們把某個 $b_i$ 加上 $x$，那 $s$ 會怎麼改變？以下新的 $b$ 和 $s$ 我們記作 $b'$ 和 $s'$。

假設 $b$ 是 $[3,1,4,1,5,9]$，$s$ 就是 $[3,4,8,9,14,23]$（$s_0=0$ 就不寫出來了），我們把 $b_3$ 加上 $5$，就會得到
\[b'=[3,1,9,1,5,9] \qquad s'=[3,4,13,14,19,28]\]
發現了嗎？$s'$ 之中，$s'_3$ 以後的都加上了 $5$，前面則都不變。

也就是說，把 $b_i$ 加上 $x$ 的結果是，$s_0$ 到 $s_{i-1}$ 都不變，$s_i$ 到 $s_N$ 都加上 $x$。

如果我們把 $b_l$ 加上 $x$，再把 $b_{r+1}$ 減去 $x$（如果 $r<N$ 的話，$r=N$ 就不做這件事）……

\[
\begin{align*}
s'_{l-1} &= s_{l-1} \\
s'_{l} &= s_{l} + x \\
s'_{l+1} &= s_{l+1} + x \\
&\vdots \\
s'_r &= s_r + x \\
s'_{r+1} & = s_r + x - x = s_{r+1}
\end{align*}
\]

$s_l$ 到 $s_r$ 都被加上了 $x$、其他都不變，只修改 $b$ 的兩個元素，就可以改變 $s$ 的一個區間！

回到本來的問題，我們要支援 $q$ 次將 $a_1,a_2,\dots,a_n$ 的一個區間加上一個數值，然後輸出最終的 $a_1,a_2,\dots,a_n$。用我們剛剛的發現，要是我們有個序列 $d_1,d_2,\dots,d_n$，使得 $a$ 是 $d$ 的前綴和（特別令 $a_0=0$），那我們每個操作都只需要修改 $d$ 的兩個元素，最後再算出 $d$ 的前綴和，就是我們要的答案了！$a$ 一開始全都是 $0$，所以這個我們希望的序列 $d$ 的起始值，很明顯只要全都是 $0$ 就可以了。

如果今天問題進化一點，$a_i$ 的初始值不一定是 $0$ 呢？這樣我們就要好好找出序列 $d$ 了。這件事情其實非常容易，我們知道：

\[
\begin{align*}
a_{i-1} &= d_1 + d_2 + \dots + d_{i-1} \\
a_i &= d_1 + d_2 + \dots + d_{i-1} + d_i
\end{align*}
\]

所以 $d_i$ 就是 $a_i-a_{i-1}$ 囉。整理一下過程，一開始我們算出 $d_i=a_i-a_{i-1}$ 之後，對於每筆操作 $l,r,x$，把 $d_l$ 加上 $x$、把 $d_{r+1}$ 減去 $x$，所有操作做完以後，再算出 $d$ 的前綴和，就是最終修改完的 $a$。

這樣一來，只要在一開始和最後各花 $O(n)$ 的時間算出 $d$ 和算出 $a$，每筆操作就可以只花 $O(1)$ 的時間。

$d$ 這個序列我們稱作 $a$ 的差分序列，每個序列都是它的前綴和序列的差分序列、也是它的差分序列的前綴和序列。

我們介紹了前綴和與差分，實際上它們根本就是同一件事，只是我們在對不同的東西操作而已。它們的核心精神都是一樣的，都是在把「可能性很多」的要求，轉化成可能性比較少、更好處理的要求，用前綴和計算區間和是「將區間和變成兩個前綴和相減」，而用差分辦到區間加值是「將區間加值變成兩次的後綴加值」。