前缀和的应用场景是，需要对某个区间[i…j]频繁查询累计和，避免每次查询都遍历这个区间。差分数组的应用场景是，需要对某个区间v[i…j]频繁地加或减某一值，避免每次都遍历这个区间。 技巧：前缀和配合map，保存前缀和结果，支持后续计算中的高效查询

C++可以使用numeric中的库函数
计算某个序列局部元素的和
#include
vector vec = {};
vector arr(vec.size());
partial_sum(vec.begin(), vec.end(), arr);

一维前缀和

解决问题：长度为n的序列，m次询问，每次输入一对数a,b。输出从第a个数到第个数的和；
时间复杂度O（n+m）
计算区间和[l, r] : int sum = sums[r + 1] - sums[l];

# 一维前缀和：
vector<int> nums;
vector<int> sums(nums.size() + 1, 0); // 空间比nums大1，前缀和整体右移一位, 这样计算不需要考虑数组越界
for (int i = 0; i < nums.size(); i++) {
    sums[i + 1] = sums[i] + nums[i];
}
int sum = sums[r + 1] - sums[l];

二维前缀和

解决问题：n行m列的整数矩阵，每次查询给出x1,y1,x2,y2表示一个子矩阵的左上角坐标和右下角坐标，每次输出子矩阵中所有数的和。
计算子矩阵和[x1,y1] —> [x2, y2]：
int sum = sums[x2 + 1][y2 + 1] - sums[x2 + 1][y1] - sums[x1][y2 + 1] + sums[x1][y1];

# 二维前缀和：
vector<vector<int>> nums;
vector<vector<int>> sums(nums.size() + 1, vector<int>(nums[0].size() + 1, 0));
for (int i = 0; i < nums.size(); i++) {
    for (int j = 0; j < nums[0].size(); j++) {
        sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + nums[i][j];
    }
}
int sum = sums[x2 + 1][y2 + 1] - sums[x2 + 1][y1] - sums[x1][y2 + 1] + sums[x1][y1];

树上前缀和

从根节点到某节点的值之和
某节点及其子节点的值之和

前缀和和差分数组 - 图1
从根节点到某节点的值之和：

该场景，如何标记每个分支上的节点？可根据深度进行标记，标识节点已经访问。

差分数组

真实数组：nums[i]
差分数组：diff[i]
diff[i] = nums[i] - nums[i - 1]; // 差分数组的值为真实数据的变更值
nums[i] = diff[0] + ... + diff[i]; // 差分数组的前缀和即为真实数组
eg, 要对[i,…,j]区间内的元素整体+3，则令diff[i] += 3, diff[j + 1] -= 3即可，复杂度O(1)。

解题思路：
- 初始化差分数组：根据变更值，构造差分数组，常用map (key: 更变点，value: 变更值)
- 根据差分数组求原始数组：对差分数组求前缀和，求出的即为原始数组
- 根据原始数组判断结果

这里用map而不是vector，是因为降低空间复杂度。

例子

// 和为K的连续子数组的个数
// 前缀和 
/*
  * sums[i] = sums[i - 1] + nums[i];
  * K = sums[i] - sums[j]; 
  */
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1; // 对于一开始的情况，下标0之前没有数据，可以认为前缀和为0，个数为1
        int sums = 0;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            sums += nums[i];
            if (mp[sums - k]) { // if (mp.find(sums - k) != mp.end())
                count += mp[sums - k];
            }
            mp[sums]++; // 遍历至此，前缀和为sums的次数又多了一次
        }
        return count;
    }
};

// 航班预订统计：差分数组
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> answer(n);
        vector<int> diff(n + 1); // +1 是为了防止最后一个数计算的时候，栈溢出
        for (int i = 0; i < bookings.size(); i++) {
            diff[bookings[i][0] - 1] += bookings[i][2];
            diff[bookings[i][1] - 1 + 1] -= bookings[i][2];
        }
        answer[0] = diff[0];
        for (int i = 1; i < n; i++) {
            answer[i] = diff[i] + answer[i - 1];
        }
        return answer;
    }
};

661.图片平滑器

// 计算当前数字对应周边数字的平均值。
class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size();
        int n = img[0].size();
        vector<vector<int>> sum(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + img[i][j];
            }
        }
        vector<vector<int>> ans(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int y1 = max(j - 1, 0);
                int y2 = min(j + 1, n - 1);
                int x1 = max(i - 1, 0);
                int x2 = min(i + 1, m - 1);
                int sums = sum[x2 + 1][y2 + 1] - sum[x1][y2 + 1] - sum[x2 + 1][y1] + sum[x1][y1];
                int cnt = (y2 - y1 + 1) * (x2 - x1 + 1);
                ans[i][j] = sums / cnt;
            }
        }
        return ans;
    }
};