前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

①一维前缀和

题目：P8218 【深进1.例1】求区间和

给定 n 个正整数组成的数列 a1,a2,⋯,an 和 m 个区间 [i,j]，分别求这 m 个区间的区间和。

例如：输入 4 3 2 1 ，区间[1,4]和为10，区间[2,3]和为5。

枚举法

如上使用枚举法，时间复杂度是接近n^2,容易超时。前缀和就算先计算出1~i项的和，用数组保存。比如sum[7]代表是1~7项的和，sum[3]就算1~3项之和。所以sum[7]-sum[3]就算4~7项之和。

前缀和

②计数排序（前缀和优化）

计数排序是状态法（模拟法）一种,下标代表数字，元素代表个数，所以每输入一个数字，该数字个数增加1。例如数组[0,1,2,3,1,2]代表0有0个，1有1个，2有2个，3有3个，4有1个，5有2个。

计数

如下图，计数后通过前缀和，可明显看到1在第1位，2在第三位（访问完后，数字-1，下一个2就会变成第二位）注意：题目有两个2。所以计数排序是不稳定的。

前缀和

计算排序（前缀和）

③二维前缀和

sum[i][j]记录的是从(1，1)开始到(i，j)的正方形区间的和。

所以sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+nums[i][j];

解析： 上方+左边-左上角+现在的数字,如下图。

sum[i][j]

求（x1,y1）到（x2,y2）的区间和时，用（x2,y2）的正方形减去（x2,y1-1）的长方形，再减去（x1-1,y2）的长方形，然后加上重复减去的（x1-1,y1-1）的正方形。

二维前缀和公式

题目：P2004 领地选择（洛谷）

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地C×C 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

二维前缀和

④差分

类似于数学中的求导和积分，差分可以看成前缀和的逆运算。通过用于某一部分区间增加一定数字，如下图再【L，R】区间内增加分数c。如果增加的次数多，用枚举的方法，容易超时。

在数组中标记L位置+c，在R+1位置-c，然后再前缀和，那么数组就变成L~R区间内都增加c。

一维差分

例如：在数组【0，1，3，5，4，6，4，3】中，往区间【1，4】【2，5】中每个数都增加1.

利用差分，原理图如下，在sum数组中先标记，然后再进行前缀和，就可得到区间增加值，最后和目标数组相加，就可得到区间增加后的新数组。时间复杂度就变为m+n(相比枚举的n*m时间复杂度低)。

一维差分原理图

题目：P2367 语文成绩（洛谷）

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 n，p，代表学生数与增加分数的次数。

第二行有 n 个数，a1∼an，代表各个学生的初始成绩。

接下来 p 行，每行有三个数，x，y，z，代表给第 x 个到第 y 个学生每人增加 z 分。

一维差分（语文成绩）

⑤二维差分

和一维差分类似，也是在相应的区间标记好增加的值，然后再使用前缀和，最后数组相加。

在(x1,y1)(x2,y2)组成的长方形中每个数字都增加c。那么在sum[x1][y1]标记为+c，在

sum[x1][y2+1]和sum[x2+1][y1]中标记为-c，最后在重复增加的sum[x2+1][y2+1]的位置标记-c.

二维差分

P3397 地毯（洛谷）

题目描述

在 n×n 的格子上有 m 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 n,m。意义如题所述。

接下来 m行，每行两个坐标 (x1,y1) 和(x2,y2)，代表一块地毯，左上角是 (x1,y1)，右下角是 (x2,y2)。

输出格式

输出每个格子被多少个地毯覆盖。

思路：差分，在地毯的覆盖坐标标记好数值，然后再使用前缀和，原数组全为0，不加也可。

二维差分

所以：差分就是标记好的后的前缀和。