前缀和与差分¶

前缀和¶

前缀和是在 OI 当中一种十分重要的预处理手段，可以简单理解为前 \(i\) 个数的和。

问题

给定一个长度为 \(n\) 的序列，现在要你回答 \(m\) 个询问，每一个询问都是形如 \((l,r)\) 的形式，要你求出 \(\displaystyle\sum\limits_{i~~=~~l}^{r}a_i\)。

首先，我们可以使用暴力求解来回答这个问题。但是这样子做的时间太慢了，假如每一次询问都是 \((1,n)\) 的形式，那么暴力枚举的时间复杂度就会高达 \(\mathcal O(nm)\)。那你肯定会说，我把所有可能得询问的答案全部都记下来不久行了？那么这样子的时间复杂度也会飙到 \(\mathcal O(n^2)\)，况且万一 \(n\) 很大，那么空间也是会爆掉的。

仔细观察询问的信息，我们就可以对其进行拆解，使得这个式子里面只有 \(1\sim i\) 的和。

\[ \begin{aligned} \sum\limits_{i=l}^{r}a_i&=(a_l+a_{(l+1)}+\cdots+a_r) \\ &=(a_1+a_2+\cdots+a_r)-(a_1+a_2+\cdots+a_{(l-1)}) \\ &=\sum\limits_{i=1}^{r}a_i-\sum\limits_{i=1}^{l-1}a_i \\ \end{aligned} \]

而 \(\sum\limits_{j=1}^{i}a_j=\sum\limits_{j=1}^{i-1}a_j+a_i\)，那么我们就可以使用数组 \(p_i\) 来记录 \(\sum\limits_{j=1}^{i}a_j\)，并以 \(\mathcal O(n)\) 的时间预处理出 \(p\) 数组，而查询的时候只需要输出 \(p_r-p_{(l-1)}\) 即可。

如果你不想特殊处理 \(p_1\) 为 \(a_1\) 的话，不妨将 \(p_0\) 赋为 \(0\)，因为 \(0+x=x\)。

代码

for (int i = 1; i <= n; i++) {
  p[i] = p[i - 1] + a[i];
}
for (cin >> m; m; m--) {
  cin >> l >> r;
  cout << p[r] - p[l - 1] << '\n';
}

接下来就是解决区间相乘的问题了，询问的答案也从 \(\sum\limits_{i=l}^{r}a_i\) 变成了 \(\prod\limits_{i=l}^{r}a_i\)。既然上一次 \(+\) 我们就使用了 \(-\)，那么这一次 \(\times\) 我们该不该使用 \(\div\) 呢？反推试一下：

\[ \begin{aligned} \prod\limits_{i=1}^{r}\div\prod\limits_{i=1}^{l}&=(a_1\times a_2\times\cdots\times a_r)\div(a_1\times a_2\times\cdots\times a_{(l-1)}) \\ &=(a_l\times a_{l+1}\times\cdots\times a_r) \\ &=\prod\limits_{i=l}^{r}a_i \end{aligned} \]

看来是对的。不过一定要记得将 \(p_0\) 设为 \(1\)，因为 \(1\times x=x\)。

代码

p[0] = 1;
for (int i = 1; i <= n; i++) {
  p[i] = p[i - 1] * a[i];
}
for (cin >> m; m; m--) {
  cin >> l >> r;
  cout << p[r] / p[l - 1] << '\n';
}

因此，不管是什么运算符，只要找到它的逆运算就可以使用前缀和了。

二维前缀和¶

例题

给定 \(n\times m\) 大小的矩阵，要你回答 \(q\) 次询问，每次询问都形如 \((x_1,y_1,x_2,y_2)\)，要你求出 \(\displaystyle\sum\limits_{i=x_1}^{x_2}~\sum\limits_{j=y_1}^{y_2}~a_{i,j}\)

我们可以设 \(p_{i,j}\) 表示为 \(\displaystyle\sum\limits_{k=1}^{i}\sum\limits_{l=1}^{j}a_{k,l}\)，那么我们可以很自然地说出递推式 \(\displaystyle\sum\limits_{k=1}^{i}\sum\limits_{l=1}^{j}a_{k,l}=\sum\limits_{k=1}^{i-1}\sum\limits_{l=1}^{j}a_{k,l}+\sum\limits_{k=1}^{i}\sum\limits_{l=1}^{j-1}a_{k,l}+a_{i,j}=p_{(i-1,j)}+p_{(i,j-1)}+a_{i,j}\)，但是这样子是错误的，因为 \(\displaystyle\sum\limits_{k=1}^{i-1}\sum\limits_{l=1}^{j-1}a_{k,l}\) 会计算两次，所以我们减去 \(\displaystyle\sum\limits_{k=1}^{i-1}\sum\limits_{l=1}^{j-1}a_{k,l}\) 就行了。

代码

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
  }
}
for (cin >> m; m; m--) {
  cin >> x1 >> y1 >> x2 >> y2;
  cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1] << '\n';
}

差分¶

差分是前缀和的逆运算。

例题

有一个长度为 \(n\) 的数组，最开始全为 \(0\)。现在有 \(m\) 次修改，每一次修改都是形如 \((l,r)\) 的形式，表示将 \(l\sim r\) 当中的所有元素全部加上 \(1\)。问你最后数组变成了什么样子。

由于 \(m\) 可能会很大，但是输出序列的数量只有一次，因此我们不能直接在原数组上修改，而是使用一个差分数组来替代。假设最后的数组 \(a_i=\sum_{j=1}^{i}p_j\)，那么当 \(p_i\) 加上一就代表着 \(a_i\) 及后面的元素都加上一。同理，当 \(p_i\) 减去一就代表着 \(a_i\) 及后面的元素都减去一。

那么对于询问 \((l,r)\)，我们只需要将 \(p_l\) 加上一，再将 \(p_{r+1}\) 减去一，最后在还原数组就行了，甚至在还原的时候我们都不需要 \(a\) 数组。

代码

for (int i = 1, p; i <= m; i++) {
  cin >> l >> r;
  p[l]++, p[r + 1]--;
}
for (int i = 1; i <= n; i++) {
  cout << (p[i] += p[i - 1]) << ' ';
}

前缀和与差分¶

前缀和¶

二维前缀和¶

差分¶

评论