前缀和与差分

前缀和公式为 num[i] = num[i - 1] + a[i]
差分公式为 diff[i] = a[i] - a[i - 1]
前缀和与差分是能互相转换的
前缀和数组进行一次差分可得原数组
差分数组进行前缀和可得原数组

原数组 ---前缀和---> 前缀和数组
前缀和数组 ---差分---> 原数组
原数组 ---差分---> 差分数组
差分数组---前缀和---> 原数组

前缀和数组 <----> 原数组 <---> 差分数组

一维前缀和
题目描述
给定义一个数组𝑎，有𝑞+1次询问，对于每次询问：
给定两个整数𝑙,𝑟，求出𝑎𝑙 + 𝑎𝑙+1 + ... + 𝑎𝑟的结果。

输入描述
第一行一个整数表示样例个数T(1≤T≤10)。
对于每组样例：
第一行2个整数n(1≤n≤10^5),q(1≤q≤10^5)，分别表示数组长度和询问次数。

第二行n个整数，表示数组a(−10^9≤ai≤10^9)。

接下来q行，每行两个整数r(1≤l≤r≤n)表示询问的区间。

输出描述
对于每组样例，一行一个整数表示答案。

输入样例1
2
5 3
1 2 3 4 5
1 2
2 5
3 4
7 2
-1 9 -10 8 2 6 11
1 5
2 7
输出样例1
3
14
7
8
26

题解
根据输入的数组，建立一个每次相加前一位的数组
如输入的为1 2 3 4 5
根据前缀进行和
1，1+2=3，3+3=6，6+4=10，10+5=15
建立的数组为1 3 6 10 15
对于查询的区间（l,r）只需进行算出：r位减去（l-1）位之间的值即可
如查询（2,5）之间的和，15-1即是（2,5）区间的和

代码样例

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
void vol() {
    ll m, n; cin >> m >> n;
    vector<ll>ve(m + 1 , 0);
    for (ll i = 1; i <= m; i++) {
        cin >> ve[i];
    }
    vector<ll>cop(m + 1, 0);
    for (ll i = 1; i <= m; i++) {
        cop[i] = cop[i - 1] + ve[i];
    }
    ll l, r;
    for (ll i = 1; i <= n; i++) {
        cin >> l >> r;
        cout << cop[r] - cop[l - 1] << '\n';
    }
}
int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll t; cin >> t;
    while (t--) {
        vol();
    }
    return 0;
}

一维差分
题目描述
给定一个长度为n的数组a，和两个整数p,q。
先进行p次区间加操作：将区间[l,r]的数字都加上x。

再进行q次区间查询操作：求出[l,r]的数字之和。
对于每次区间查询操作，输出结果。
输入描述
第一行三个整数n,p,q。(1≤n≤10^5 ,0≤p≤10^5 ,0≤10^5 ≤q)

第二行n个整数表示数组a。(−10^9 ≤ai ≤10^9 )

接下来p行，每行三个整数l,r,x。(1≤l≤r≤n,−10^9 ≤x≤10^9 )

接下来q行，每行两个整数(1≤l≤r≤n)

输出描述
对于每次区间查询操作，输出结果。

输入样例1
5 1 2
1 1 1 2 2
1 4 2
1 3
1 5
输出样例1
9
15

题解
根据输入的数组建立一个差分数组
如输入1,2,3,4,5
1-0=1，2-1=1，3-2=1，4-3=1，5-4=1
因此建立的差分数组为1,1,1,1,1

代码实例

#include<iostream>
using namespace std;
const int N = 1e5+9;
using ll = long long;
ll a[N], diff[N], num[N];
int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n , p , q ; cin >> n >> p >> q ;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1];
    
    while (p--) {
        ll l, r, x; cin >> l >> r >> x;
        diff[l] += x; diff[r + 1] -= x;
    }

    for (int i = 1; i <= n; i++) a[i] = diff[i] + a[i - 1];
    for (int i = 1; i <= n; i++) num[i] = num[i - 1] + a[i];
    
    while (q--) {
        ll l, r; cin >> l >> r;
        cout << num[r] - num[l - 1] << '\n';
    }

    return 0;
}

二维前缀和
二维数组基本原理与一维前缀和几乎相同
注意重叠部分即可

题目描述
给定一个n行m列的整数矩阵。 q个询问，每个询问格式为：x1,y1,x2,y2，表示一个子矩阵的左上角和右下角的坐标。
对于每个询问，请回答子矩阵的所有数之和。

输入格式
第一行包括三个整数n,m,q（1≤n,m≤10^3 ，1≤𝑞≤10^5,1≤q≤10^5 ）。
接下来n行，每行包括m个整数，表示整数矩阵（每个整数的取值范围为[1,10^5 ]）。
接下来q行，每行包括四个整数x1,y1,x2,y2(1<=x1<=x2<=n,1<=y1<=y2<=m)，表示一个询问的左上角、右下角坐标。

输出格式
共q行，第i（1≤i≤q）行输出第i个询问的结果。

样例输入1
7 3 2
3 5 1
6 2 4
7 9 10
4 3 6
3 9 9
6 10 1
9 10 4
2 2 7 3
2 1 4 2
样例输出1
77
31

代码实例

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m, q; cin >> n >> m >> q;
    vector<vector<ll> >a(n + 1, vector < ll >(m + 1, 0));
    ll i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    vector<vector<ll> >b(n + 1, vector < ll >(m + 1, 0));
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1];
        }
    }
    
    while (q--) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1] << '\n';
    }

    return 0;
}

二维差分
题目描述
给定一个n行m列的整数矩阵。
有q个操作，每个操作格式为：x1,y1,x2,y2,c，其中(𝑥1,𝑦1)、(x2,y2)
分别表示一个子矩阵的左上角和右下角的坐标，每个操作将对应的子矩阵的每个元素加上c。

请输出进行完所有操作后的矩阵。

输入描述
第一行包括三个整数n,m,q（1≤n,m≤10^3 ,1≤q≤10^5 ）。

输出描述
共n行，每行包括m个整数，表示进行完所有操作后的矩阵。

输入样例1
4 3 3
1 5 1
3 3 2
5 3 4
4 4 2
1 2 1 2 2
2 1 2 3 2
4 2 4 3 1
输出样例1
1 7 1
5 5 4
5 3 4
4 5 3

代码示例

//二维差分
#include<iostream>
using namespace std;
using ll = long long;
const int N = 1e3 + 9;

ll a[N][N], diff[N][N];

int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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];
        }
    }
    //差分
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            diff[i][j] += a[i][j];
            diff[i + 1][j] -= a[i][j];
            diff[i][j + 1] -= a[i][j];
            diff[i + 1][j + 1] += a[i][j];
        }
    }
    //修改
    while (q--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        diff[x1][y1] += c; 
        diff[x2 + 1][y2 + 1] += c;
        diff[x2 + 1][y1] -= c;
        diff[x1][y2 + 1] -= 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] + diff[i][j];
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }

    return 0;
}