前缀和

一个数组的前缀和可以理解为从数组开头到该位置的和。

利用前缀和可以 Θ(1)\Theta(1) 的时间复杂度完成查询。

前缀和用于查询一个序列的区间和。

一维前缀和

一维前缀和可以在 Θ(n)\Theta(n) 的时间复杂度完成统计。

si=∑j=1iaj=si−1+ais_i=\sum_{j=1}^{i}a_j=s_{i-1}+a_i

∑i=lrai=sr−sl−1\sum_{i=l}^{r}a_i=s_r-s_{l-1}

二维前缀和

二维前缀和可以在 Θ(nm)\Theta(nm) 的时间复杂度完成统计。

si,j=∑k=1i∑l=1jak,l=si−1,j+si,j−1−si−1,j−1+ais_{i,j}=\sum_{k=1}^{i}\sum_{l=1}^{j}a_{k,l}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_i

∑i=x1x2∑j=y1y2ai,j=sx2,y2+sx1−1,y1−1−sx2,y1−1−sx1−1,y2\sum_{i=x1}^{x2}\sum_{j=y1}^{y2}a_{i,j}=s_{x2,y2}+s_{x1-1,y1-1}-s_{x2,y1-1}-s_{x1-1,y2}

差分

一个数组的差分可以理解为数组中相邻两个数据的差。

对差分数组求前缀和即可得到原数组。

利用差分可以 Θ(1)\Theta(1) 的时间复杂度完成修改。

前缀和用于快速修改序列中的区间，并在所有修改完成后读取。

一维差分

si={a1,i=1ai−ai−1, 2≤i≤ns_i=\begin{cases}a_1,i=1\\a_i-a_{i-1},\ 2 \le i \le n\end{cases}

实际编程中若 ii 从 11 起则无需考虑 i=1i=1 的特殊情况。

将区间 [l,r][l,r] 增加 zz 可以转化为 sl=sl+z,sr+1=sr+1−zs_l=s_l+z,s_{r+1}=s_{r+1}-z。

二维差分

si,j={a1,1, i=1,j=1a1,j, i=1,2≤j≤mai,1, 2≤i≤n,j=1ai,j−ai−1,j−ai,j−1+ai−1,j−1, 2≤i≤n,2≤j≤ms_{i,j}=\begin{cases}a_{1,1},\ i=1,j=1\\a_{1,j},\ i=1,2 \le j \le m\\a_{i,1},\ 2 \le i \le n,j=1\\a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1},\ 2 \le i \le n,2 \le j \le m\end{cases}

实际编程中若 i,ji,j 从 11 起则无需考虑前三种特殊情况。

将区间 [(x1,y1),(x2,y2)][(x_1,y_1),(x_2,y_2)] 增加 zz 可以转化为 sx1,y1=sx1,y1+z,sx2+1,y2+1=sx2+1,y2+1+z,sx1,y2+1=sx1,y2+1−z,sx2+1,y1=sx2+1,y1−zs_{x_1,y_1}=s_{x_1,y_1}+z,s_{x_2+1,y_2+1}=s_{x_2+1,y_2+1}+z,s_{x_1,y_2+1}=s_{x_1,y_2+1}-z,s_{x_2+1,y_1}=s_{x_2+1,y_1}-z。