【算法基础】前缀和差分初步

引入

• 【3】前缀和 [CCF NOI 大纲（2025 修订版）- 2.1.4.4]
• 【4】差分 [CCF NOI 大纲（2025 修订版）- 2.1.4.4]

前缀和差分算法是解决维护区间和、区间加问题常用的一种预处理方式。对于前缀和差分算法，OI 中经常与图论中的树和最近公共祖先（LCA）联合考察。此先介绍算法初步。

一维前缀和

前缀和通常用于预处理区间和。

\(\textbf{Definition}\) 对于一个序列 \(a\)，前 \(n\) 个元素的前缀和为 \(b_i=\sum\limits_{i=1}^{n} a_i = b_{i-1} + a_i\)。
\(\textbf{Property 1}\) 令前缀和数列 \(b_i=\sum\limits_{k=1}^{i} a_k = b_{i-1} + a_i\)，区间 \([l,r]\) 的和对前缀和数列 \(b\) 有 \(\sum\limits_{i=l}^{r} a_i = b_{r} - b_{l-1}\)。
\(\textbf{Proof 1}\) \(\sum\limits_{i=l}^{r} a_i = \sum\limits_{i=1}^r a_i - \sum\limits_{i=1}^{l-1} a_i = \sum\limits_{i=l}^{r} a_i = b_{r} - b_{l-1}\)。

一维区间和

求区间和
给定 \(n\) 个正整数组成的数列 \(a_1, a_2, \cdots, a_n\) 和 \(m\) 个区间 \([l_i,r_i]\)，分别求这 \(m\) 个区间的区间和。

运用 \(\textbf{Property 1}\) 即可做到单次询问 \(\Theta(1)\)。

一维差分

差分类似于前缀和的逆运算。差分通常用于预处理区间加。

\(\textbf{Definition}\) 钦定 \(a_0 = 0\)，对于一个序列 \(a\)，前 \(n\) 个元素的差分为 \(b_i=\Delta_{i=1}^{n} a_i = a_i - a_{i-1}\)。
\(\textbf{Property 2.1}\) 钦定 \(a_0 = 0\)，令差分数列 \(b_i = a_i - a_{i-1}\)，则 \(a_i = \sum\limits_{j=1}^i b_j\)。
\(\textbf{Proof 2.1}\) \(a_i = a_1 + \sum \Delta = \sum\limits_{j=1}^i b_j\)。
\(\textbf{Property 2.2}\) 钦定 \(a_0 = 0\)，令差分数列 \(b_i = a_i - a_{i-1}\)，则 \(\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n (n-i+1)b_i\)。
\(\textbf{Proof 2.2}\) \(\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}b_j=\sum\limits_{i=1}^n(n-i+1)b_i\)。

一维区间加

有一个由 \(n\) 个元素组成的数列 \(a\)。你需要维护 \(k\) 个 \([l_i,r_i]\) 区间加 \(p_i\) 的操作，然后求操作后的数列 \(a\)。

\(\textbf{Proposition 4}\) 令 \(b\) 为差分序列，则对于操作 \([l_i,r_i]\) 而言，令 \(b_l\gets b_l+p_i,b_{r+1} \gets b_{r+1}-p_i\)，再对 \(b\) 作前缀和即可。
\(\textbf{Proof 4}\) 由于差分序列记录的是元素的变化量，所以对 \(b_i \gets b_i + \Delta\) 会作用在 \(a\) 上使 \([i,n]\) 范围内的量都增加 \(\Delta\)。同理，对 \(b_j \gets b_j - \Delta\) 会作用在 \(a\) 上使 \([j,n]\) 范围内的量都减少 \(\Delta\)。如果我们将 \(i\) 视作 \(l\)，\(j\) 视作 \(r\textcolor{red}{+1}\)（原因是效应在 \([l,r]\) 范围内而非 \([l,r)\) 范围内，如果 \(j=r\) 会使 \(a_r\) 的值多 \(\Delta\)），则可以维护这个过程。

对于维护区间加问题，差分是一种常见的维护方式。

二维前缀和

\(\textbf{Definition}\) 对于一个矩阵 \(A\)，根据容斥原理，第 \(n\) 行 \(m\) 列元素的前缀和为 \(B_{i,j}=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} A_{i,j} = B_{i-1,j} + B_{i,j-1} + B_{i-1,j-1} + A_{i,j}\)。

二维矩阵和

有一个由 \(n\times m\) 个元素组成的矩阵 \(A\)。你需要维护 \(k\) 个 \([(x_1,y_1),(x_2,y_2)]\) 子矩阵求和的操作，然后求操作后的矩阵 \(A\)。

\(\textbf{Proposition 5}\) 令前缀和矩阵 \(B_{i,j} = B_{i-1,j} + B_{i,j-1} + B_{i-1,j-1} + A_{i,j}\)，子矩阵 \([(x_1,y_1),(x_2,y_2)]\) 的和对前缀和矩阵 \(B\) 有\(\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2} b_{i,j} = b_{x_2,y_2} - b_{x_{1} - 1,y_2} - b_{x_2 - 1,y_{1} - 1} + b_{x_{1} - 1,y_{1} - 1}\)。
\(\textbf{Proof 5}\) 容斥原理易证。

容易做到单次询问 \(\Theta(1)\)。

二维差分*

二维矩阵加

有一个由 \(n\times m\) 个元素组成的矩阵 \(A\)。你需要维护 \(k\) 个 \([(x_1,y_1),(x_2,y_2)]\) 子矩阵加 \(p_i\) 的操作，然后求操作后的矩阵 \(A\)。

\(\textbf{Proposition 6}\) 对于二维差分矩阵 \(B\)，每次区间加的操作可以拆分为

\[B_{x_1,y_1} \gets B_{x_1,y_1} + p_i \]

\[B_{x_1,y_1 + 1} \gets B_{x_1,y_1 + 1} - p_i \]

\[B_{x_2,y_1} \gets B_{x_2,y_1} - p_i \]

\[B_{x_2 + 1,y_2 + 1} \gets B_{x_2 + 1,y_2 + 1} + p_i \]

这四项贡献进行计算，再令 \(\Delta\) 为 \(B\) 的二维前缀和，则操作后的矩阵 \(\mathscr{A}_{i,j} = A_{i,j} + \Delta_{i,j}\)。
\(\textbf{Proof 6}\) 通过 \(\textbf{Proposition 4}\) 可以证明拆分贡献的正确性，通过 \(\textbf{Proposition 5}\) 可以证明实现的二维前缀和的方法和正确性，通过容斥原理可以合并贡献计算及证明正确性。证从略。

最近修改时间是 \(2025.8.25\)。