前缀和 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}$

习题
T225501	USACO Silver	Subsequences Summing to Sevens	2016	普及-
T222196		地毯		普及-
P1387		最大正方形		普及/提高-
T222195	HNOI	激光炸弹	2003	普及/提高-
T222194		Poetize6 IncDec Sequence		普及+/提高
P3128	USACO Plat	Max Flow	2015	普及+/提高
P1314	NOIP-S	聪明的质监员	2011	普及+/提高
CF1458A	CF	Row GCD		普及+/提高
T222198	NOIP-S	组合数问题	2016	普及+/提高
P6146	USACO Gold	Help Yourself	2020	普及+/提高
T222197		三步必杀		提高+/省选-
CF1110E	CF	Magic Stones		提高+/省选-