5.4.1 前缀和数组

对于一个数组 int a[]，有前缀和数组 int prefix[]，令

5.4 前缀与差分 - 图1

即前缀和数组上的元素，对应原数组对应位置元素和它之前所有元素的和。利用前缀和数组可以把查询原数组任意 5.4 前缀与差分 - 图2 区间和的 5.4 前缀与差分 - 图3#card=math&code=O%28n%29&id=FKMtr) 遍历操作转化为两次 5.4 前缀与差分 - 图4#card=math&code=O%281%29&id=D4DL8) 查询前缀和数组操作，即

5.4 前缀与差分 - 图5

使用前缀和仍然需要遍历原数组一次，预处理出前缀和数组。在题目频繁询问区间和时，前缀和数组是一种常用且功能强大的优化。

在使用前缀和数组时，通常把原数组的起始下标设为 5.4 前缀与差分 - 图6 ，避免边界值特殊判断。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 4;
  4. int a[N], f[N];
  5. int n, m;
  6. int main() {
  7.     cin >> n >> m;
  8.     // 原数组从 1 开始读入
  9.     for (int i=1; i<=n; ++i) {
  10.         cin >> a[i];
  11.     }
  12.     // 计算前缀和数组
  13.     for (int i=1; i<=n; ++i) {
  14.         f[i] = f[i - 1] + a[i];
  15.     }
  16.     // m 次询问
  17.     while (m--) {
  18.         int l, r;
  19.         cin >> l >> r;
  20.         cout << f[r] - f[l - 1] << endl;
  21.     }
  22.     return 0;
  23. }

实际操作时，如果不需要保留原数组，则可以直接在原数组上更新。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int a[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
    }
    // 覆盖为前缀和数组
    for (int i=1; i<=n; ++i) {
        a[i] += a[i - 1];
    }
    // m 次询问
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << a[r] - a[l - 1] << endl;
    }
    return 0;
}

例题：牛客 14556. 数圈圈

题目描述

tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。 现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。 顺便还数了a到b之间有多少个圈。

但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。 但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。

输入描述: 输入一个T，表示数据组数 每组测试数据包含两个正整数a，b。 T∈[1,50] a,b∈[1,106]

输出描述: 每组数据输出结果，并换行。

样例输入 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 100

样例输出 0 0 0 1 0 1 0 2 1 1 111

备注: 数字的圈的个数请根据样例自行理解。

参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 4;
int c[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};    // 0~9 单个数字的圆圈数
int f[N];    // 前缀和数组
int t;
// 求数 x 中所有数字的圆圈数
int getC(int x) {
    int res = 0;
    while (x) {
        res += c[x % 10];
        x /= 10;
    }
    return res;
}
int main() {
    // 预处理
    for (int i=1; i<N; ++i) {
        f[i] = f[i - 1] + getC(i);
    }
    cin >> t;
    // while 循环回答 t 组询问的简便写法，相当于 for (int i=0; i<t; ++i)
    // 节省了 i 的命名，缺点是不再保存原有 t 的值
    while (t--) {
        int a, b;
        cin >> a >> b;
        cout << f[b] - f[a - 1] << endl;
    }
    return 0;
}

此题中没有写出原数组，但仍然是前缀和的基本思想。

代码中 getC() 的写法是按位拆数的常见写法，需要熟练掌握。这个写法通用于任何进制。

按位拆数练习（可能需要「位运算」基础知识）：力扣 剑指 Offer 15. 二进制中1的个数

5.4.2 差分数组

与前缀和相似，差分数组能够降低区间修改的复杂度。差分数组保存当前项与前项的差值，使

5.4 前缀与差分 - 图7

当对一整段区间进行更新，使其中每一项值增加 5.4 前缀与差分 - 图8 时，原数组需要进行 5.4 前缀与差分 - 图9#card=math&code=O%28n%29&id=lOkrk) 遍历操作，而在差分数组的意义上，只有区间两端的两点需要改变，即区间第一个元素相较前一项增加了 5.4 前缀与差分 - 图10 ，区间最后一项的后一项较前一项增加了 5.4 前缀与差分 - 图11 。也就是 5.4 前缀与差分 - 图12#card=math&code=O%281%29&id=orfCp) 操作：

void update(int l, int r, int k) {
    diff[l] += k;
    diff[r + 1] -= k;
}

进行过所有修改后，我们需要把它还原成原数组，对差分数组做求前缀和数组操作即可。

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

事实上，差分是前缀和的逆运算，是不是很神奇？

// 一维差分
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int a[N], s[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
    }
    // 求差分数组
    for (int i=1; i<=n; ++i) {
        s[i] = a[i] - a[i - 1];
    }
    // m 次修改
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        s[l] += c;
        s[r + 1] -= c;
    }
    // 恢复数组并输出
    for (int i=1; i<=n; ++i) {
        s[i] += s[i - 1];
        cout << s[i] << ' ';
    }
    return 0;
}

注意事项和前缀和同样，数组下标尽量从 5.4 前缀与差分 - 图13 开始，初始化需要 5.4 前缀与差分 - 图14#card=math&code=O%28n%29&id=KFwlB) 时间，单次修改时间复杂度为 5.4 前缀与差分 - 图15#card=math&code=O%281%29&id=wVGV7)。

例题：力扣 1109. 航班预订统计

力扣要求返回数组的长度必须为 5.4 前缀与差分 - 图16，此题中如何处理越界的预订值得思考。请参考官方题解。

参考代码
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans(n);
        for (auto& booking : bookings) {
            ans[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                ans[booking[1]] -= booking[2];
            }
        }
        for (int i=1; i<n; ++i) {
            ans[i] += ans[i - 1];
        }
        return ans;
    }
};

5.4.3 二维前缀和

这一类操作当然可以扩展到二维。你可以理解为询问矩阵的内元素的和，理解公式用到简单的图像会更加直观。可以参考：浅谈二维前缀和

二维前缀和模板

#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
int a[N][N];
int n, m, q;
int main() {
    cin >> n >> m >> q;
    for (int i=1; i<=n ;++i) {
        for (int j=1; j<=m; ++j) {
            cin >> a[i][j];
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            // 不覆盖的写法
            // f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i - 1][j - 1];
        }
    }
    while (q--) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int res = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
        cout << res << endl;
    }
    return 0;
}

例题：AcWing 99. 激光炸弹

地图上有 5.4 前缀与差分 - 图17 个目标，用整数 5.4 前缀与差分 - 图18 表示目标在地图上的位置，每个目标都有一个价值 5.4 前缀与差分 - 图19。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 R×RR×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 5.4 前缀与差分 - 图20 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 5.4 前缀与差分 - 图21 和 5.4 前缀与差分 - 图22，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 5.4 前缀与差分 - 图23 行，每行输入一组数据，每组数据包括三个整数 5.4 前缀与差分 - 图24，分别代表目标的 5.4 前缀与差分 - 图25 坐标，5.4 前缀与差分 - 图26 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

5.4 前缀与差分 - 图27
5.4 前缀与差分 - 图28
5.4 前缀与差分 - 图29
5.4 前缀与差分 - 图30

输入样例：

2 1 0 0 1 1 1 1

输出样例：

1

题目用到标准的二维前缀和，但有一些细节需要注意。

参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5004;
int a[N][N];
int n, r;
int main() {
    cin >> n >> r;
    while (n--) {
        int x, y, w;
        cin >> x >> y >> w;
        a[++x][++y] += w;    // 下标范围改成[1,5001]，方便前缀和；+= 是因为不同目标可能在同一位置。
    }
    r = min(5001, r);    // 炸弹范围超过5001（全覆盖），按照5001计算
    // 计算前缀和数组
    for (int i=1; i<=5001; ++i) {
        for (int j=1; j<=5001; ++j) {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    int ans = 0;
    // 遍历所有边长为 r、右下顶点为(i, j)的正方形
    for (int i=r; i<=5001; ++i) {
        for (int j=r; j<=5001; ++j) {
            // 尝试用当前正方形面积更新答案
            int sum = a[i][j] - a[i - r][j] - a[i][j - r] + a[i - r][j - r];
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

5.4.4 二维差分 *

现在需要频繁地进行矩阵修改。还是用到差分数组。理解公式参考：差分——（2）二维差分

差分数组上的修改操作

// (x1, y1)为左上角
void update(int x1, int y1, int x2, int y2, int c) {
    s[x1][y1] += c;
    s[x2 + 1][y2 + 1] += c;
    s[x2 + 1][y1] -= c;
    s[x1][y2 + 1] -= c;
}

不过，初始的二维差分数组如何求得？我们当然可以再提出二维差分由原数组得来的公式；但是换一种角度，在没有读入题目数据时，初始差分矩阵就是我们新建的全零二维数组。当我们每读入一个数组元素时，就把它当成一次对差分数组的更新操作，即：

int a[N][N];    // 原数组
int s[N][N];    // 差分数组
for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
        cin >> a[i][j];
        update(i, j, i, j, a[i][j]);
    }
}

这样做的时间复杂度仍然是 5.4 前缀与差分 - 图31#card=math&code=O%281%29&id=JNfvZ)。

同样，进行过所有修改后，我们需要把它还原成原数组，对二维差分数组做求二维前缀和数组操作即可。

例题：MYOJ 5227. 二维差分模板——区间修改

参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
int s[N][N];
int n, m, q;
void update(int x1, int y1, int x2, int y2, int c) {
    s[x1][y1] += c;
    s[x2 + 1][y2 + 1] += c;
    s[x2 + 1][y1] -= c;
    s[x1][y2 + 1] -= c;
}
int main() {
    cin >> n >> m >> q;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            int num;
            cin >> num;
            update(i, j, i, j, num);    // 插入代替初始化
        }
    }
    // q 次更新
    while (q--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        update(x1, y1, x2, y2, c);
    }
    // 还原并输出
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            // 二维前缀和，求原矩阵
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            if (j > 1) cout << ' ';    // 严谨输出，控制行末空格
            cout << s[i][j];
        }
        cout << endl;
    }
    return 0;
}

代码中放弃了原数组，这是因为本题中不需要保留原数组，于是我们一边读入下一个数字，一边更新差分数组。

在输出时，要注意「输出的严谨性」。当题目有多行输出，如 cout << s[i][j] << " "; 的语句，会在换行前留下一个多余的空格，这在部分 OJ 会被判为「格式错误（Presentation Error）」。所以我一般采取上面代码的方法，改为在非首元素的前面输出空格，有时需要一个额外的 bool head; 记录是否遇到过首元素。掌握输出是一项基本功。这一点在后续代码中还会得到体现。

拓展练习（难度较高）：[USACO 2017 Ope P]Modern Art