前缀和与差分

概念讲解

前缀和

前缀和是指数组前 i 个元素的和。

一维前缀和：
$$S[i] = a[0] + a[1] + ... + a[i] = S[i-1] + a[i]$$

区间和查询：
$$\sum_{i=l}^{r} a[i] = S[r] - S[l-1]$$

差分

差分是前缀和的逆运算。

差分数组：
$$d[i] = a[i] - a[i-1]$$

区间修改： 将 [l, r] 区间的每个元素加上 c
$$d[l] += c, d[r+1] -= c$$

一维前缀和

构建

12345678int a[N], prefix[N];
int n;

// 构建前缀和
prefix[0] = a[0];
for (int i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] + a[i];
}

查询

12345// 查询区间 [l, r] 的和
int query(int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];
}

二维前缀和

构建

12345678910int a[N][N], prefix[N][N];
int n, m;

// 构建二维前缀和
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 
                      - prefix[i-1][j-1] + a[i][j];
    }
}

查询

12345// 查询子矩阵 [(x1,y1), (x2,y2)] 的和
int query(int x1, int y1, int x2, int y2) {
    return prefix[x2][y2] - prefix[x1-1][y2] 
         - prefix[x2][y1-1] + prefix[x1-1][y1-1];
}

差分数组

构建

12345678int a[N], diff[N];
int n;

// 构建差分数组
diff[0] = a[0];
for (int i = 1; i < n; i++) {
    diff[i] = a[i] - a[i - 1];
}

区间修改

12345// 将 [l, r] 区间的每个元素加上 c
void update(int l, int r, int c) {
    diff[l] += c;
    diff[r + 1] -= c;
}

还原数组

1234// 还原数组
for (int i = 1; i < n; i++) {
    diff[i] += diff[i - 1];
}

二维差分

区间修改

1234567// 将子矩阵 [(x1,y1), (x2,y2)] 的每个元素加上 c
void update(int x1, int y1, int x2, int y2, int c) {
    diff[x1][y1] += c;
    diff[x2 + 1][y1] -= c;
    diff[x1][y2 + 1] -= c;
    diff[x2 + 1][y2 + 1] += c;
}

还原数组

123456// 还原数组
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
    }
}

考点分析

初赛考查方式

1. 选择题： 前缀和的计算
2. 程序阅读： 理解前缀和的构建过程
3. 编程题： 前缀和应用

常见题型

• 区间和查询
• 区间修改
• 二维矩阵问题

例题精讲

例题 1：区间和查询

题目： 给定数组，多次查询区间 [l, r] 的和。

解答：

1234567891011121314151617181920212223#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    
    long long a[n + 1], prefix[n + 1];
    prefix[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
    
    return 0;
}

例题 2：差分应用

题目： 将数组的 [l, r] 区间每个元素加上 c。

解答：

12345678910111213141516171819202122232425262728293031#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    long long a[n + 1], diff[n + 2];
    fill(diff, diff + n + 2, 0);
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        diff[i] = a[i] - a[i - 1];
    }
    
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        diff[l] += c;
        diff[r + 1] -= c;
    }
    
    // 还原数组
    for (int i = 1; i <= n; i++) {
        diff[i] += diff[i - 1];
        cout << diff[i] << " ";
    }
    cout << endl;
    
    return 0;
}

练习题

1. 洛谷 P1115 最大子段和

12345678910111213141516171819#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long long prefix = 0, minPrefix = 0, ans = -1e18;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        prefix += x;
        ans = max(ans, prefix - minPrefix);
        minPrefix = min(minPrefix, prefix);
    }
    
    cout << ans << endl;
    return 0;
}

2. 洛谷 P3397 地毯

1234567891011121314151617181920212223242526272829#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    int diff[n + 2][n + 2] = {0};
    
    while (m--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        diff[x1][y1]++;
        diff[x2 + 1][y1]--;
        diff[x1][y2 + 1]--;
        diff[x2 + 1][y2 + 1]++;
    }
    
    // 还原数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            cout << diff[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

3. 洛谷 P2004 旅行投资

1234567891011121314151617181920212223242526272829303132333435#include <iostream>
using namespace std;

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    
    long long a[n + 1][m + 1], prefix[n + 1][m + 1] = {0};
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] 
                          - prefix[i - 1][j - 1] + a[i][j];
        }
    }
    
    long long ans = -1e18;
    int x = 1, y = 1;
    
    for (int i = c; i <= n; i++) {
        for (int j = c; j <= m; j++) {
            long long sum = prefix[i][j] - prefix[i - c][j] 
                          - prefix[i][j - c] + prefix[i - c][j - c];
            if (sum > ans) {
                ans = sum;
                x = i - c + 1;
                y = j - c + 1;
            }
        }
    }
    
    cout << x << endl << y << endl;
    return 0;
}

易错点

⚠️ 注意：

1. 前缀和数组下标从 1 开始可以简化计算
2. 二维前缀和要注意容斥原理
3. 差分还原后才是原数组
4. 注意边界条件