开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 前缀和和差分 -> 正文阅读

[C++知识库]前缀和和差分

前缀和和差分

1. 前缀和和差分原理

原理

前缀和和差分都是分为一维和二维。

前缀和

前缀和数组要求下标从1开始，这样方便计算。
一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

差分：为了将区间操作变为单点操作

一维差分

A是原数组，B是差分数组，给区间A[l, r]中的每个数加上c，等价于：B[l] += c, B[r + 1] -= c

二维差分

A是原数组，B是差分数组，给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c，等价于：
B[x1, y1] += c, B[x2 + 1, y1] -= c, B[x1, y2 + 1] -= c, B[x2 + 1, y2 + 1] += c

2. AcWing上的前缀和和差分题目

AcWing 795. 前缀和

问题描述

问题链接：AcWing 795. 前缀和

分析

一维前缀和模板题。
使用a记录原数组，使用s表示a的前缀和数组，即s[i]=a[1]+a[2]+...+a[i]。
则区间l~r之间的元素之和为s[r] - s[l-1]。

代码

#include <cstdio>

const int N = 100010;

int n, m;
int a[N], s[N];

int main() {
    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    
    return 0;
}

AcWing 796. 子矩阵的和

问题描述

问题链接：AcWing 796. 子矩阵的和

分析

二维前缀和模板题。
数据初始读入到s中，然后在s的基础上计算二维前缀和，即s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]。
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]。

代码

#include <cstdio>

const int N = 1010;

int n, m, q;
int s[N][N];

int main() {
    
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &s[i][j]);
    
    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];
    
    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    
    return 0;
}

AcWing 797. 差分

问题描述

问题链接：AcWing 797. 差分

分析

差分的技巧一般可以用于解决区间同时加/减去一个数的情况，差分可以将此操作变为两个单点操作。
原数组是a（假设a[1]是第一个元素，a[0]未使用），则可以根据a计算出差分数组，计算公式如下：

$\\ b[2] = a[2] - a[1] \\ ... \\ b[n] = a[n] - a[n-1]$

差分数组求前缀和可以得到原数组。
a是原数组，b是差分数组，给区间a[l, r]中的每个数加上c，等价于：b[l] += c, b[r + 1] -= c。

代码

#include <cstdio>

const int N = 100010;

int n, m;  // 数组长度，查询个数
int a[N];

int main() {
    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    // 差分数组初始化
    for (int i = n; i; i--) a[i] -= a[i - 1];
    
    while (m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        a[l] += c, a[r + 1] -= c;
    }
    
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    
    // 输出结果
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    
    return 0;
}

AcWing 798. 差分矩阵

问题描述

问题链接：AcWing 798. 差分矩阵

分析

给定原矩阵a[i, j]，构造差分矩阵b[i, j]，使得a[][]是b[][]的二维前缀和。
a是原数组，b是差分数组，给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c，等价于：b[x1, y1] += c, b[x2 + 1, y1] -= c, b[x1, y2 + 1] -= c, b[x2 + 1, y2 + 1] += c。
如何根据a数组推出b数组呢？初始b为全0，然后直接遍历一遍a，在b插入对应元素即可。

代码

#include <cstdio>

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    
    scanf("%d%d%d", &n, &m, &q);
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            insert(i, j, i, j, a[i][j]);
        }
    
    for (int i = 0; i < q; i++) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    
    // 根据差分数组求原数组
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) printf("%d ", a[i][j]);
        puts("");
    }
    
    return 0;
}

AcWing 99. 激光炸弹

问题描述

问题链接：AcWing 99. 激光炸弹

分析

本题相当于让求解一个(R-1)*(R-1)的子矩阵的和的最大值，因为目标的坐标在[0~5000]之间，因此可以使用一个二维数组存储每个位置的价值。
因为前缀和需要空出(0, 0)，因此读入数据的时候横纵坐标加上一个1的偏移量。

代码

#include <iostream>

using namespace std;

const int N = 5010;

int n, R;
int s[N][N];

int main() {
    
    scanf("%d%d", &n, &R);
    R = min(5001, R);
    
    for (int i = 0; i < n; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x++, y++;
        s[x][y] += w;
    }
    
    // 求二维前缀和
    for (int i = 1; i <= 5001; i++)
        for (int j = 1; j <= 5001; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    
    int res = 0;
    for (int i = R; i <= 5001; i++)
        for (int j = R; j <= 5001; j++)
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
    
    printf("%d\n", res);
    
    return 0;
}

AcWing 100. 增减序列

问题描述

问题链接：AcWing 100. 增减序列

分析

因为本题最终变为的数一定在int范围内，因此不会出现高精度的问题。
本题需要考虑原数组a的差分数组b，原数组a全部为0，等价于：差分数组b中b[1]任意，b[2]~b[n]全部为0。
因此转化之后问题变为了：（1）至少操作多少次，可以使得b[2]~b[n]全部为0；（2）有多少中结果，等价于b[1]有多少种值。
对原数组a[1]~a[n]的操作会影响b[1]~b[n+1]一共n+1个数。我们将对数组a的操作根据范围分为四大类：

（1） $\le l \le r \le n-1$ ：让b[2]~b[n]中某个数加一，另一个数减一；

（2） $\le n-1$ ：b[1]加一（减一），b[2]~b[n]中的某个数减一（加一）；

（3） $\le l， r = n$ ：b[2]~b[n]中的某个数减一（加一），b[n+1]加一（减一）；

（4） $l = 1, r = n$ ：相当于让数组a中所有元素加一或者减一，无意义。
为了使得b[2]~b[n]全部变为0，我们尽量使用第（1）中操作，即如果b[2]~b[n]中既有正数又有负数，可以使用操作（1），否则如果只有正数或者负数使用操作（2）或者（3）即可。
对于差分数组b[2~n]，首先求出所有正数的和p，再求出所有负数绝对值的和q，可以使用第（1）中操作min(p, q)次，还剩余|p-q|的正数或者负数，可以使用操作（2）或（3），因此最少的操作次数为min(p, q) + |p-q|=max(p, q)。
因为最后剩余|p-q|次操作，这些操作可以是（2）或者（3），操作（2）会改变b[1]的值，因此b[1]可以取|p-q|+1种取值。

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N];

int main() {
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = n; i; i--) a[i] -= a[i - 1];
    
    LL p = 0, q = 0;
    for (int i = 2; i <= n; i++)
        if (a[i] > 0) p += a[i];
        else q -= a[i];
    
    printf("%lld\n", max(p, q));
    printf("%lld\n", abs(p - q) + 1);
    
    return 0;
}

3. 力扣上的前缀和和差分题目

Leetcode 0303 区域和检索 - 数组不可变

题目描述：Leetcode 0303 区域和检索 - 数组不可变

在这里插入图片描述

分析

本题的考点：前缀和。
前缀和下标都是从1开始的。
因为本题中数组中的数据不变，因此可以使用一个数组s记录原数组nums的前缀和，即s[i]表示nums前i个数据之和。
有了数组s，则如果要求解nums[i...j]之间的元素和，则首项让i++, j++最后返回s[j]-s[i-1]即可。

代码

class NumArray {
public:

    vector<int> s;

    NumArray(vector<int> &nums) {

        int n = nums.size();
        s.resize(n + 1);
        for (int i = 0; i < n; i++) s[i + 1] = s[i] + nums[i];
    }

    int sumRange(int i, int j) {
        i++, j++;
        return s[j] - s[i - 1];
    }
};

Java

class NumArray {

        private int[] s;  // sum[i]存储前i个元素和， sum[0] = 0

        public NumArray(int[] nums) {

            s = new int[nums.length + 1];
            s[0] = 0;
            for (int i = 1; i < s.length; i++) s[i] = s[i - 1] + nums[i - 1];
        }

        public int sumRange(int i, int j) {
            i++; j++;
            return s[j] - s[i - 1];
        }
    }

时空复杂度分析

时间复杂度：初始化是 $O (n)$ ，n为数组长度；sumRange是 $O (1)$ 的。
空间复杂度： $O (n)$ 。

Leetcode 0304 二维区域和检索 - 矩阵不可变

题目描述：Leetcode 0304 二维区域和检索 - 矩阵不可变

在这里插入图片描述

分析

本题的考点：二维前缀和。
前缀和下标都是从1开始的。
这里使用二维数组s[i][j]表示从左上角(0, 0)到(i-1, j - 1)这个 $\times j$ 矩形中的数据之和，数组s可以递推求解，递推公式如下：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1]。
求出s后，如果让我们求出(x1, y1)到(x2, y2)之间矩形中的元素和，则首先让x1++, y1++, x2++, y2++，然后返回s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]即可。

代码

class NumMatrix {
public:
    vector<vector<int>> s;

    NumMatrix(vector<vector<int>> &matrix) {

        if (matrix.empty() || matrix[0].empty()) return;

        int n = matrix.size(), m = matrix[0].size();
        s = vector<vector<int>>(n + 1, vector<int>(m + 1));
        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] + matrix[i - 1][j - 1];
    }

    int sumRegion(int x1, int y1, int x2, int y2) {
        x1++, y1++, x2++, y2++;
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    }
};

Java

class NumMatrix {

    int[][] s;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;

        int n = matrix.length, m = matrix[0].length;
        s = new int[n + 1][m + 1];
        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] + matrix[i - 1][j - 1];
    }
    
    public int sumRegion(int x1, int y1, int x2, int y2) {
        x1++; y1++; x2++; y2++;
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    }
}