第四章：前缀和、差分与离散化

区间问题中的重复工作通常来自两处：不同询问重复累加相同元素，或者不同修改反复访问相同位置。前缀和预先保存累计结果，差分只记录影响开始和结束的位置；当坐标很大而实际出现的坐标很少时，再用离散化压缩存储。

阅读前需要掌握数组下标与排序。本章先讨论全部读入后统一处理的情形；每次修改后立即查询的问题需要重新分析，不能默认沿用静态表。

1. 一维前缀和

例题：求区间和。

简易题面：给定长度为 $n$ 的正整数序列和 $m$ 个区间，分别求每个区间内所有元素的和。

数据范围：$1\le n,m\le10^5$；$1\le a_i\le10^4$；$1\le l\le r\le n$。

每次询问逐项相加，最坏需要 $O(nm)$ 时间。两个询问可能反复使用同一个前缀，因此先保存从起点累加的结果。定义

$$p_i=\sum_{j=1}^{i}a_j,\qquad p_0=0.$$

程序用 $pre[i]$ 保存 $p_i$。本题所有元素为正，总和最多为 $10^9$，全局 $\texttt{int }a[100010],pre[100010]$ 足够。以下先建立前缀表：

pre[0] = 0;
for (int i = 1; i <= n; ++i)
{
    pre[i] = pre[i - 1] + a[i];
}

从前 $r$ 项的和中删去前 $l-1$ 项，剩下的恰好是闭区间 $[l,r]$：

$$\sum_{i=l}^{r}a_i=p_r-p_{l-1}.$$

每读到一个合法询问 $l,r$，直接计算：

int ans = pre[r] - pre[l - 1];

前缀和预处理 $O(n)$，每次询问 $O(1)$。

设数组为 $[3,-1,4,2]$，逐项累加后得到：

下标 $i$	0	1	2	3	4
$pre[i]$	0	3	2	6	8

要查询 $[2,4]$，先取前四项的和 $8$，再减去区间开始前的第一项前缀 $3$，得到 $5$。被减去的是 $[1,l-1]$，因此下标必须是 $l-1$。这个小例子用于展示公式，前缀和本身允许负数，不依赖单调性。

如果有 $q$ 次询问，逐段累加最坏是 $O(nq)$，先建立前缀和后为 $O(n+q)$。但修改一个原数组元素，会影响它之后的全部前缀；普通前缀和主要用于预处理之后数组保持不变的查询。

边界前缀 $pre[0]$

当 $l=1$ 时，公式需要访问 $pre[0]$。把它设为 $0$ 后，无须为第一段单独分支。

$pre[0]$ 表示“一个元素也没有取时的和”，不是多放了一个真实元素。很多算法中的第 $0$ 个状态都承担这种边界作用；先赋予它明确含义，公式就能同时处理普通位置和边界位置。

2. 二维前缀和

例题：领地选择。

简易题面：给定一个 $n$ 行 $m$ 列的价值地图，要选择一个边长为 $c$ 的正方形区域，使区域内所有格子的价值和最大。保证最优方案唯一。

数据范围：$1\le n,m\le1000$；$1\le c\le\min(n,m)$；每个格子价值的绝对值不超过 $32767$。

逐个计算每个候选正方形需要重复扫描其内部格子。改为预存每个左上角矩形的和，就能用固定次数的加减求任意矩形和。

定义 $p_{i,j}$ 为左上角 $(1,1)$ 到 $(i,j)$ 的矩形和，程序存于 $pre[i][j]$。本题总和绝对值最多约为 $3.28\times10^{10}$，所以 $pre$ 必须为 $\texttt{long long}$；输入 $a$ 使用 $\texttt{int}$。全局数组至少覆盖 $1001\times 1001$ 个位置，第零行、零列保持为零。以下按行、列递增执行：

pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];

查询左上角 $(x_1,y_1)$、右下角 $(x_2,y_2)$：

long long ans = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];

减去两块多余区域后，左上角重叠部分被减了两次，所以要加回来。

可以把 $pre[i-1][j]$ 看成上面的矩形，把 $pre[i][j-1]$ 看成左边的矩形。两者相加，左上交集被算了两次，减去一次后再补上右下角当前格子，就得到整块前缀矩形。

例如矩阵两行为 $[1,2,3]$ 和 $[4,5,6]$，整个矩形和为 $21$。查询两行的第 2～3 列，减去第一列的前缀和 $5$，结果是 $16$。若同时排除上方和左方，则按代码把两者交集加回来。第 $0$ 行和第 $0$ 列都应初始化为 $0$。

固定大小的正方形可以枚举一个角，用四次前缀访问求和；预处理和枚举均为 $O(nm)$。若格子值允许为负，最大答案应从一个实际矩形的和或足够小的值开始，不能默认 $0$ 可行。

3. 差分

3.1 差分数组

例题：语文成绩。

简易题面：有 $n$ 名学生，第 $i$ 名学生初始成绩为 $a_i$。接下来进行 $p$ 次修改，每次给编号 $x$ 到 $y$ 的所有学生增加 $z$ 分。

请输出全部修改完成后的最低成绩。

数据范围：$1\le n\le5\times10^6$；$0\le p\le n$；$0\le a_i,z\le100$；$1\le x\le y\le n$。

若逐次修改每名学生，最坏需要 $O(np)$ 次更新。相邻两名学生若同时加分，他们的成绩差不变，因此可以只记录区间两端的变化。定义 $d_1=a_1$，且 $d_i=a_i-a_{i-1}$。

本题单个最终成绩不超过 $100+100p\le500000100$，差分及还原值都可用 $\texttt{int}$。数组 $a,d$ 应在全局声明，容量至少为 $5000002$，预留第 $n+1$ 个位置；两个数组约占 $40$ MB，仍须与实际内存限制核对。

d[1] = a[1];
for (int i = 2; i <= n; ++i)
{
    d[i] = a[i] - a[i - 1];
}

给区间 $[l,r]$ 每个数增加 $x$：

d[l] += x;
d[r + 1] -= x;

所有修改完成后，先令 $a[0]=0$，再用前缀和还原：

for (int i = 1; i <= n; ++i)
{
    a[i] = a[i - 1] + d[i];
}

差分适合“多次区间修改，最后统一询问”。

两个端点以外的差分无需修改：当 $[l,r]$ 同时增加 $x$ 时，区间内部相邻两项都增加 $x$，它们的差不变；$l$ 相比前一项多了 $x$；$r+1$ 本身不变，但它的前一项增加了 $x$，所以差要减少 $x$。

例如原数组 $[2,2,5,1]$ 的差分为 $[2,0,3,-4]$。给 $[2,3]$ 加 $4$，只把差分的第 2 项加 $4$、第 4 项减 $4$，得到 $[2,4,3,-8]$；重新累加得到 $[2,6,9,1]$。

批量修改时，每次只记录两处变化，最后统一还原，总复杂度为 $O(n+p)$。还原前必须让 $a[0]=0$；若每次修改后都立即还原整个数组，就失去了批量处理的优势。仅求最终最小值时，还原过程中顺便维护最小值即可。

3.2 前缀和与差分的关系

• 差分记录相邻变化；
• 对差分做前缀和得到原数组；
• 对原数组做差分得到变化量。

两者的联系也可以从相消理解：$d[1]+\cdots+d[i]$ 中，相邻的 $+a[j]$ 与 $-a[j]$ 逐项抵消，最后只留下 $a[i]$。前缀和把变化累积成状态，差分把状态拆成变化，这比单独记忆两组代码更容易迁移到新问题。

4. 频次前缀

值域较小时，先统计每个值出现次数，再对频次累加。以下是两个阶段的关键更新式：第一行用于遍历输入，第二行用于按正数值递增建表；它们不是同一轮循环中的连续操作。$cnt$、$pre$ 为足够覆盖值域的全局 $\texttt{int}$ 数组，初始为零。

++cnt[a[i]];
pre[x] = pre[x - 1] + cnt[x];

这样可以快速回答某个数值区间中有多少元素。

这里下标从“原数组的位置”变成了“某个数值”。若数组为 $[1,3,3,5]$，询问值在 $[2,4]$ 中的元素个数，应统计两次出现的 $3$，结果是 $2$；它与原数组第 2～4 个位置的元素个数没有关系。

若值域包含 $0$，可以令 $pre[0]=cnt[0]$，对 $x\ge 1$ 再累加；查询下界为 $0$ 时直接取 $pre[R]$，不访问负下标。另一种方法是统一把数值映射到一号下标，关键是建表与查询使用同一约定。

5. 离散化

简单问题：坐标排名。

简易题面：给定 $n$ 个整数。将所有不同的整数从小到大排列，并依次编号为 $1,2,3,\ldots$。

请输出原序列中每个整数对应的编号。相同整数的编号相同。

数据范围：$1 \le n \le 2\times 10^5$；$-10^9 \le a_i \le 10^9$。

直接按原值开桶可能需要数十亿个位置，但真正出现的不同值至多有 $n$ 个。只需保留大小关系时，可以按值排序，并让相等值共享同一名次。为了回到原输入顺序，把值 $x$ 与原编号 $id$ 放在同一个结构体中；全局数组 $a$ 保存记录，$ans$ 保存每个原位置的名次。

sort(a + 1, a + n + 1, cmp);
int m = 0;
for (int i = 1; i <= n; ++i)
{
    if (i == 1 || a[i].x != a[i - 1].x)
    {
        ++m;
    }
    ans[a[i].id] = m;
}

比较函数 $cmp$ 只按 $x$ 升序排列。排序后每遇到一个新值才增加名次，因而相等值编号相同，较小值编号也较小。例如 $100,7,100,1000000$ 映射为 $2,1,2,3$。排序和扫描共需 $O(n\log n)$ 时间，记录与答案共需 $O(n)$ 空间。

排名只保留顺序，不保留距离。原坐标 $100$ 与 $1000000$ 相差 $999900$，其排名只差 $1$。计算实际长度时必须保留原坐标；第六章还会介绍用二分查找取得已有值的排名。

6. 区间事件

简单问题：热水供应。

简易题面：一台设备每分钟最多供应 $W$ 单位热水。第 $i$ 个用户会在时刻区间 $[S_i,T_i)$ 内每分钟使用 $P_i$ 单位热水。

热水不能储存。请判断设备能否在所有时刻满足全部用户的计划。

数据范围：$1\le n\le2\times10^5$；$0\le S_i<T_i\le2\times10^5$；$1\le W,P_i\le10^9$。

区间 $[l,r]$ 可以看成：

• 在 $l$ 处开始；
• 在 $r+1$ 处结束。

把所有事件按位置排序并扫描，是差分思想向扫描线的自然延伸。本题热水用量最多可累计到 $2\times10^{14}$，差分及当前用量必须使用 $\texttt{long long}$；容量较小并不能保证超额时的累计量也小。

上面的 $r+1$ 约定适用于整数闭区间。热水供应问题使用的时间段是左闭右开 $[l,r)$，应在 $r$ 处撤销影响。若用 $[2,5)$ 表示占用，则时刻 $5$ 已不在该段中。

若改为查询一段整数位置中有多少位置的覆盖次数达到门槛，先用差分还原每个位置的覆盖次数，再把“覆盖次数达到要求”转成 $0/1$，最后对这个布尔数组做前缀和。这样每个询问统计的是达标位置数，不是覆盖次数总和。每一次变换后都要重新说明数组含义。

7. 二维差分

例题：地毯。

简易题面：在 $n\times n$ 的方格上依次放置 $m$ 个矩形。第 $i$ 个矩形覆盖左上角 $(x_1,y_1)$ 到右下角 $(x_2,y_2)$ 的所有格子。

请输出每个格子被多少个矩形覆盖。

数据范围：$1\le n,m\le1000$；$1\le x_1\le x_2\le n$；$1\le y_1\le y_2\le n$。

若逐格修改矩形，每次都要访问矩形面积数量的元素。把一维的“开启与撤销”分别沿两维组合，就只需改四个角。以下 $d$ 为全局差分数组，初始为零，容量覆盖第 $n+1$ 行与第 $n+1$ 列；元素类型应容纳所有修改量叠加后的值。给闭矩形 $[x_1,x_2]\times[y_1,y_2]$ 全部增加 $v$：

d[x1][y1] += v;
d[x2 + 1][y1] -= v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y2 + 1] += v;

所有修改完成后，对 $d$ 做二维前缀和即可还原每个位置的最终值。

四个标记可以按影响方向理解：左上角开启增加；越过下边界后取消；越过右边界后也取消；右下外侧同时经历了两次取消，需要补回一次。恢复时每个位置接收其左上方全部标记的累积影响。

若原矩阵全零，可以直接累积修改标记后还原；若已有初始值，要么先构造初始矩阵的二维差分，要么把还原出的增量加回原矩阵，二者选择一种。本题是方阵，数组两维都需覆盖下标 $n+1$；$m$ 表示矩形数量，不能用作列数。每次修改取 $v=1$，覆盖次数不超过 $m$，可使用 $\texttt{int}$。总时间为 $O(m+n^2)$，空间为 $O(n^2)$。

8. 位置与边的差分

例题：NOIP 2005 普及组·校门外的树。

简易题面：位置 $0$ 至 $L$ 各有一棵树，移走若干闭区间内的树，求剩余数量。

数据范围：$1\le L\le10000$，区间数 $1\le m\le100$，$0\le l\le r\le L$。

第一章逐个标记位置，已经能够通过原题。用差分时，每段只在 $d[l]$ 加一、$d[r+1]$ 减一，再从位置 $0$ 开始累计覆盖次数；累计值为零的位置仍有树。这把 $O(mL+L)$ 改为 $O(m+L)$，重叠区间只会增加覆盖次数，不会重复扣除树。全局差分数组应覆盖下标 $0$ 至 $L+1$，初始全零。

统计路径经过的边时，端点约定有所不同。从站点 $2$ 到站点 $5$ 经过三条边；以边的较小端点编号，应给 $[2,4]$ 加一，即在 $2$ 开始、在 $5$ 撤销。反向行走经过同样的边。先说明统计的是点还是边，再决定差分端点，不能一律给两个站点之间的闭区间加一。

9. 作业

巩固练习

• 求区间和
• NOIP 2005 普及组·校门外的树
• 地毯

提高训练

• 领地选择
• 语文成绩