前缀和

数组a = [a1,a2,…,an]
前缀和数组s = [s1,s2,…,sn] 其中si = a1+a2+…+ai

1.如何求s[i]

使用迭代的方法

s[0] = 0;
for(int i=1;i<=n;i++)
    s[i] = s[i-1]+a[i];

2.前缀和数组的作用

在O(1)时间内求出原数组中[l,r]一段区间内的和s[r]-s[l-1]

3.模版

m次询问,求数组a第l个数字到第r个数字的和

const int N = 100010;
int n, m;
int a[N], s[N]; // 全局数组s[0]已经被初始化了

int main(){

    scanf("%d%d", &n, &m);

    // 初始化原数组，注意下标从1开始存储
    for (int i = 1; i <= n; i ++ ){
        scanf("%d", &a[i]);
    }

    // 前缀和的初始化，注意下标从1开始迭代
    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;

}

4.二维前缀和

sij 为 原二维数组aij为顶点围成的矩形内所有元素和

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

作用：求一个子矩阵[x1,y1]~[x2,y2]的所有元素和
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
模版：

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 ++ ){
        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, 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;

}

差分

数组a = [a1,a2,…,an]
差分数组b = [b1,b2,…,bn] 满足ai = b1+b2+…+bn

1.如何求b[i]

b1 = a1
b2 = a2-a1
b3 = a3-a2
b4 = a4-a3
…
(其实数组a可以称作数组b的前缀和数组，数组b称为数组a的差分数组)

s[0] = 0;
for(int i=1;i<=n;i++)
    s[i] = s[i-1]+a[i];

2.前缀和数组的作用

在O(1)时间内让原数组中[l,r]区间内的所有元素+c
b[l] += c b[r + 1] -= c

3.模版

m次询问,使得数组a第l个到第r个元素+c

const int N = 100010;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

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++ ) {
        insert(i, i, a[i]);
        /*
        假定a数组最开始都是0，
        那么b数组初始时就是a数组的差分数组了，
        对于a数组每一个位置i，相当于插入了一个数a[i]。
        */
       b[i] = a[i]-a[i-1];
       /*
       从差分数组的定义出发，
       这里a数组已经初始化完成，
       b数组假定0。
       */

    }

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

4.二维前缀和

aij 为 数组bij为顶点围成的矩形内所有元素和

for (int i = 1; i <= n; i++ ) {
        for (int j = 1; j <= m; j++)
        {
            insert(i,j,i,j,a[i][j]);
        }
    }

作用：使得数组a子矩阵[x1,y1]~[x2,y2]内所有元素+c
b[x1][y1] += c b[x2 + 1][y1] -= c b[x1][y2 + 1] -= c b[x2 + 1][y2 + 1] += c;
模版：

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[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= 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]);
        }
    }

    for (int i = 1; i <= n; i++ ) {
        for (int j = 1; j <= m; j++)
        {
            insert(i,j,i,j,a[i][j]);
        }
    }

    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++){
            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;
}