Skip to content

前缀和 Prefix Sum

通过预处理计算出数组的前缀的和，可以大大降低一些查询操作的复杂度，是一种重要而常用的优化。

一维数组的前缀和是最常见的，计算方法也直接，\(O(n)\)时间内完成。

二维和多维的前缀和可以使用容斥原理(Inclusion Exclusion Principle)来计算。例如二维：

\(sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}\)

差分

差分与前缀和相对：

定义：\(b_i=\begin{cases}a_i-a_{i-1}\,&i \in[2,n] \\ a_1\,&i=1\end{cases}\)

习题