【基础算法篇】前缀和与差分

前缀和

什么是前缀和

1. 原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
2. 前缀和 Si为数组的前 i项和，即前缀和为： S[i] = a[1] + a[2] + a[3] + … + a[i]

前缀和的作用

快速求出元素组中某段区间的和

一维数组求解前缀和

1. for循环求出 每个S[i] (将 S[0] 定义为 0, 避免下标的转换)
2. 求 [l, r]中的和, 即为 S[r] - S[l-1]

AC代码

#include

using namespace std;
const int N = 100010;
int a[N], sum[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 ++ )
{
    sum[i] = sum[i - 1] + a[i];
}

while (m -- )
{
    int l, r;
    cin >> l >> r;
    cout << sum[r] - sum[l - 1] << endl;
}
return 0;

}

二维前缀和（有点像概率论的二维分布函数计算方法）

公式

不给太多解释 详细可以查网上更好的解释

两个公式

1. 求前缀和公式
   S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]

2. 求区间公式 (x1, y1) 到 (x2, y2)
   S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1][y1 - 1]

AC代码

#include <iostream>

using namespace std;
const int N = 1010;
int a[N][N], S[N][N];

int main()
&#123;
    int n, m, q;
    cin >> n >> m  >> q;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        &#123;
            cin >> a[i][j];
            S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + a[i][j];
        &#125;   

    while (q -- )
    &#123;
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1] << endl;
    &#125;
    return 0;
&#125;

差分

什么是差分

首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];

使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组

差分用处

给定区间[l ,r ]，让我们把a数组中的[l, r]区间中的每一个数都加上c，
即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;

暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。

有没有更高效的做法吗? 考虑差分做法。

公式理解

1. 首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c;

2. 然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;

AC代码一

#include <iostream>

using namespace std;
const int N = 1000010;
int n, m;
int a[N], b[N];

int main()
&#123;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    // 构造差分数组
    for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];

    while (m -- )
    &#123;
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c;
        b[r + 1] -= c;
    &#125;

    // 还原
    for (int i = 1; i <= n; i ++ )
    &#123;
        b[i] = b[i - 1] + b[i];
        cout << b[i] << " "; 
    &#125;
    return 0;
&#125;

AC代码二（y总的方法利用insert构造b数组）

/*方法二*/
#include <iostream>

using namespace std;
const int N = 1000010;
int n, m;
int a[N], b[N];

// 使用insert函数构造b[N]
void insert(int l, int r, int c)
&#123;
    b[l] += c;
    b[r + 1] -= c;
&#125;

int main()
&#123;
     cin >> n >> m;
     for (int i = 1; i <= n; i ++ )
     &#123;
         cin >> a[i];
         insert(i, i, a[i]);
     &#125;

    while (m -- )
    &#123;
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    &#125;
    // 还原
    for (int i = 1; i <= n; i ++ )
    &#123;
        b[i] = b[i - 1] + b[i];
        cout << b[i] << " "; 
    &#125;
    return 0;
&#125;