前缀和

前缀和数组s[ ]，即数列的前 n 项和，作用是快速求出数列中连续一段数字的总和，降低算法复杂度

前缀和的求法很简单，以下只放一小段代码

for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

求其中一小段 l 到 r 中的所有数的和。

s[r] - s[l - 1]

二维前缀和

在一个二维的矩阵中同样可以使用前缀和来简便地计算某一个矩形的和

前缀和数组 s[i][j]表达的意思是以点(i , j)为右下角坐标，以零点为左下角坐标的矩形的和，利用这个定义得出以下代码，是每一个坐标的二维前缀和数组

1	s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

利用这个求出任意矩形的和 ( x1 , y1) 和 ( x2 , y2) 确定的矩形的和

1	s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])

附上一个求子矩阵的模板题及代码

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

#include <iostream>

const int N = 1010;

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

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)    //前缀和和差分一般都以1为下标和，方便统一方法
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; //求前缀和数组
        }

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

差分

差分和前缀和是一组逆运算。

计算差分的前缀和就可以得到原数组，计算原数组的前缀和就可以得到前缀和数组

差分就是一个数组中相邻两个数的差值，使用差分可以快速便捷地将数组的某一连续段的每一个全部加上一个相同的值，不需要遍历每一个数。

使用一道例题来解释形式和用法

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c l,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N]; //定义数组和差分数组
int n, m;

void insert ( int l , int r , int c) //插入操作，作用有二
{									 //一   初始化差分数组，相当于把每一个数插入全部为0的数组
    b[l] += c ;						 //二   插入，使某段 l r 之间的所有数都加上 c
    b[r + 1] -= c ;					 //原理： 将l处的差分加上一个数，使用差分的前缀和计算原数组的时候，l后的所有数都加上c
}									 //		  将 r+1 处的差分减去 c 抵消了后续所有数加上的 c ， 保持不变
									 //       最终达到只在此段全部加 c 的目标

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);			////初始化差分数组
        insert( i , i, a[i]);
    }

    while( m --)
    {
        int l , r , c ;
        scanf("%d%d%d" , &l , &r , &c);//进行插入
        insert( l , r, c);
    }

    for ( int i = 1; i <= n ; i++) //对差分进行前缀和求原数组
    {
        b[i] += b[i - 1];		
        printf( "%d " , b[i]);
    }
    return 0;
}

二维差分（差分矩阵）

改变二维差分的意义：以此坐标为左上角确定的矩阵中所有数都加或减去 c ，

实现方法与二维前缀和相似，加加减减的。似乎有容斥原理的思想。

代码模板：

#include <iostream>

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]);	//初始化差分数组
        }

    while (q--)
    {
        int x1, x2, y1, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); //进行q次操作
        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];//使用差分的前缀和计算原数组
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }

    return 0;
}

SnowDawn'Home

前缀和与差分

前缀和

二维前缀和

差分

二维差分（差分矩阵）