一维前缀和

• 假设有一个数组：a[i]
• 前缀和Si = a1 + a2 + a3 + a4 + … + ai

前缀和的作用

• 求出数组a[i]中下标[l,r]区间的和

如何求前缀和

• 公式：S[r] - S[l-1]

• 注意：下标从1开始，初始化S[0] = 0；

• 这样的好处是：若直接求S[i]，即求区间[1,i]的和，也适用这个公式，S[i] - S[0] = S[i] - 0

例题：原题链接

//数据规模大，用scanf来读，速度快很多
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int s[N];
int n,m;
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;
}

动态规划：石子合并那题也用到了前缀和

二维前缀和

S[i][j] 表示点ij及其左上角所有元素的和

如何求前缀和

S[i][j] = S[i-1][j] + S[i][j-1] -S[i-1][j-1] + a[i][j]
S[i-1][j-1]的部分是被加了两次的，所以要减掉一次，画个图就懂了

如何求部分和，即以(x1,y1)为左上角坐标、(x2,y2)为右下角坐标的子矩阵的所有数的和

S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]

例题：原题链接

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];
int s[N][N];
int n,m,q;
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]);

    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] + a[i][j];  //求前缀和

    while(q--)
    {
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);  //计算子矩阵的和
    }
    return 0;
}

差分

• 差分其实就是前缀和的逆运算

• 设有一个b数组，使得a数组是b数组的前缀和数组，b就称为a数组的差分数组。

• ai = b1 + b2 + b3 + b4 + …… + bi

• 如果我们想让a数组下标[l,r]区间的所有数加上一个数字c，我们只需要让b[l]+c,b[r+1]-c。从而实现O(n)变成O(1)

• 解释：比如我们想让下标[3,5]区间的a数组元素都加上c，因为a[3] = b[1] + b[2] + b[3]，a[4] = b[1] + b[2] + b[3] + b[4]，a[5] = b[1] + b[2] + b[3] + b[4] + b[5]，当我们把b[3] = b[3] + c，显而易见，a[3]a[4]a[5]都会加上c，因为他们的计算式里都有b[3]；除此之外，数组a后面的所有元素都会加上c，不满足我们只在区间[3,5]的元素+c的要求，这时候我们只需要让b[r+1] -= c，这样后面的元素计算的时候就会加一个c减一个c，比如a[6] = b[1] + b[2] + b[3] + c + b[4] + b[5] + b[6] - c

构造差分数组b[i]：

a[0] = 0
b[1] = a[1] - a[0]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
b[n] = a[n] - a[n-1]
可以看出，a[n] = b[1]+ b[2] + b[3] + …… + b[n]

例题：原题链接

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
void insert(int l, int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++) 
    {
        cin>>a[i];
        b[i] = a[i] - a[i-1];  //差分数组的构造
    }

    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        b[l] += c;
        b[r + 1] -= c;
    }
    for(int i = 1;i<=n;i++)
    {
        a[i] = a[i-1] + b[i];  //sum[i] = sum[i-1] + a[i]。前缀和数组sum就是a，b就相当于这里的a
    }
    for(int i = 1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

当然你也可以不用管这个b是怎么构造的

• 也可以不用管怎么构造，你不是可以通过修改b数组的两个元素实现对某个区间都加上c吗,那就做n次这个操作，从a数组初始值全为0，每次这个操作就针对一个区间长度为1的区间，即一个元素.也就是说在[i,i]区间，加上a[i]，这样把a数组的值填好了之后b数组就完成了，b数组变成什么样我不用管。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
void insert(int l, int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    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++) a[i] = a[i-1] + b[i];  //用自己作为前缀和
    for(int i = 1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

二维差分

• 使一个子矩阵内的元素各自加上c
• 当b[x1][y1] += c,二维数组a(x1,y1)右下角的所有元素都会加上c。但是我们只想要右下角到(x2,y2)的矩阵范围加上c，所以b[x2+1][y1] -= c且b[x1][y2+1] -= c，明显有一块减多了，所以b[x2+1][y2+1] += c
• 所以核心公式就是4个式子：
• b[x1][y1] += c
• b[x2+1][y1] -= c
• b[x1][y2+1] -= c

• b[x2+1][y2+1] += c

• 对数组b的初始化也是不用管怎么构造，原理跟一维差分一样。

原题链接

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N],b[N][N];
int n,m;
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];

    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            insert(i,j,i,j,a[i][j]);   //初始化差分数组b

    while(q--)
    {
        int x1,y1,x2,y2,c;
        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++)
            a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i][j];  //二维前缀和公式

    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
        {
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }

    return 0;
}