前缀和定义

  • 前缀和（Prefix Sum）是一种重要的预处理技术，能在O(1)时间内查询区间和，在算法竞赛和面试中应用广泛。以下是前缀和的主要应用场景和变种：

    1. 基本前缀和

  • 计算$\Sigma_{i=1}^n a_i$的值，用来求区间和

例如：

1
2
3
4
5
6
7
// 一维前缀和
vector<int> pre(n+1, 0);
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i-1] + a[i];
}
// 查询区间[l, r]的和
int sum = pre[r] - pre[l-1];

2. 二维前缀和

用于计算矩阵的和$\Sigma{i=1}^n\Sigma{j=1}^na_{ij}$

1
2
3
4
5
6
7
8
vector<vector<int>> pre(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        pre[i][j] = a[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
    }
}
// 查询子矩阵(x1,y1)-(x2,y2)的和
int sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];

前面两个的例题比较多，则行里就不举例了。

3. 前缀和与哈希表结合

这是最常用的变种，用于解决”区间和为k的区间个数”问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countSubarrays(vector<int>& nums,int k) {
    unordered_map<int,int> mp; // 前缀和 -> 出现次数
    mp[0] = 1; // 空数组的前缀和为0
    int sum=0,count=0;
    // sum拿来求前缀和，count求和为k的次数
    for(int num:nums){
        sum+=num;
        // sum - target = pre[j]  => pre[j] = sum - k
        if(mp.find(sum-k)!=mp.end())
            count+=mp[sum-k];
        mp[sum]++;
    }
    return count;
}

上面的代码思路解释，首先，先计算前缀和的值，然后加到map里面，之后看有没有出现过sum-k这种前缀和，如果有，那么这一段的和就是k了，且有$mp[sum-k]$个，这样就计算出了答案

例如：K-大师和他的领域
这一题要我们找存在几个区间满足既含有k又满足k是这个区间的中位数。
那么步骤：
1.令小于k的为-1，大于k的为1，等于k的为0
2.计算前缀和，统计前缀和一样的区间，这样区间内的和为0，说明k是这个区间的中位数，再使用$\Sigma{i=1}^{map.size()}C{m_i}^2$计算总数就行了，这样得到可能的区间。
3.但是还要保证区间内包含k，所以找到k位置，在两个k间的需要再用相同方法计算一次，
4.最后减去即可

就是说，要统计合法区间时，都可以把题目的要求变形一下，然后就可以使用这个思路了

4. 前缀和与差分数组

差分数组用于区间修改，单点查询：
这一个没什么好说的，就是差分和前缀的互逆关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 初始化差分数组
vector<int> diff(n+2, 0);
diff[1] = a[1];
for (int i = 2; i <= n; i++) {
    diff[i] = a[i] - a[i-1];
}
// 区间[l, r]增加val
void rangeAdd(int l, int r, int val) {
    diff[l] += val;
    diff[r+1] -= val;
}
// 恢复原数组
for (int i = 1; i <= n; i++) {
    a[i] = a[i-1] + diff[i];
}

5. 前缀最大/最小值

1
2
3
4
5
6
7
8
9
10
// 前缀最大值
vector<int> preMax(n+1, INT_MIN);
for (int i = 1; i <= n; i++) {
    preMax[i] = max(preMax[i-1], a[i]);
}
// 后缀最小值
vector<int> sufMin(n+2, INT_MAX);
for (int i = n; i >= 1; i--) {
    sufMin[i] = min(sufMin[i+1], a[i]);
}

6. 前缀异或和

用于处理区间异或问题：

1
2
3
4
5
6
vector<int> xorPre(n+1, 0);
for (int i = 1; i <= n; i++) {
    xorPre[i] = xorPre[i-1] ^ a[i];
}
// 区间[l, r]的异或和
int xorsum = xorPre[r] ^ xorPre[l-1];

7.二维差分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 初始化二维差分
vector<vector<int>> diff(m+2, vector<int>(n+2, 0));
// 子矩阵(x1,y1)-(x2,y2)增加val
void rangeAdd2D(int x1, int y1, int x2, int y2, int val) {
    diff[x1][y1] += val;
    diff[x2+1][y1] -= val;
    diff[x1][y2+1] -= val;
    diff[x2+1][y2+1] += val;
}
// 恢复原矩阵
vector<vector<int>> res(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + diff[i][j];
    }
}

然后很重要的一点是，有时可能是假设前缀和数组，最后再反推原数组来进行构造。