前缀和｜差分

前缀和

什么是前缀和

前缀和数组a[i]代表的是从数组下标1 - i 的和，我们可以通过ai的含义从而推出某一段区间内的sum

一维前缀和

假如我们想要得到i 到j范围内的和

我们已知a数组，我们可以求出S数组

S[I]数组代表的是从1 - i a数组的和

公式为s[j] - s[i - 1]

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N],s[N];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    
    for(int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];
    
    while(m--) {
        int l,r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}

二维前缀和

假如我们想要求二维矩阵中(x1,y1) --> (x2,y2)覆盖的面积

求部分面积公式：s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

构建前缀和公式：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + as[i][j];

询问两间覆盖面积案例

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int as[N][N],s[N][N];
int main(){
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cin >> as[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] + as[i][j];
        }
    }
    
    while(q--) {
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;
    }
    
    return 0;
}

差分

正所谓差分就是前缀和的逆运算，在前缀和中我们使用a数组来构建s数组，但是在查分中满足的条件为a[i] = b[1] + b[2] + ... + b[i]

一维差分

根据a[i] = b[1] + ... + b[i]的特性，我们可以对某一段区间内的值进行修改。

假如我们想要对l 到r区间内的值全体 + c，那么我们让b[l] + c会让>=l的所有a[i]都加上c，同理我们让b[r + 1] - c，会让>=r + 1的所有a[i] - c，这样就保证了在l 到 r的区间内的所有值加上了c

题目：将整数序列l到r区间内的所有值加上c

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N],b[N];

void insert(int l,int r,int x) {
    b[l] += x;
    b[r + 1] -= x;
}
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    
    for(int i = 1;i <= n;i++) insert(i,i,a[i]);
    
    while(m--) {
        int l,r,c;
        cin >> l >> r >> c;
        insert(l,r,c);
    }
    
    for(int i = 1;i <= n;i++) b[i] += b[i - 1];
    
    for(int i = 1;i <= n;i++) cout << b[i] << " ";
    cout << endl;
    return 0;
}

二维差分

二维差分和一维差分一样是让矩阵的部分面积加上c

如果我们想要让(x1,y1) -> (x2,y2)之间的面积每一个单元格上加上c，根据一维我们会发现让某一个位置上的值 + c同时也会影响后面的值加上c

二维差分公式

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;
}

矩阵部分 + c例题

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
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(){
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }
    
  	//构建差分矩阵b，使得b的前缀和等于a数组
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            insert(i,j,i,j,a[i][j]);
        }
    }
    int x1,y1,x2,y2,c;
    while(q--) {
        cin >> 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++) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }
    
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}