【算法与数据结构】——前缀和，差分

柔光的暖阳◎ 2022-09-11 03:18 183阅读 0赞

参考博客[二维差分][Link 1]  
[差分——（2）二维差分][2]

# 前缀和 #

给定一个数组a,如果有一个数组p，p\[i\] = p\[i-1\]+a\[i\]，这个数组p就是a的前缀和数组，p\[b\]就表示数组a的前b项和。p\[b\]-p\[a-1\]就表示数组a的\[a,b\]区间的和。

# 一维差分 #

给一个数组a,有一个数组p，p\[i\] = a\[i\]-a\[i-1\]，这个数组p就是a的差分数组。

我们可以看出前缀和数组的差分数组就是原数组

差分数组单独使用也是有意义的，比如将原数组看做是一个前缀和数组，它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。譬如使 \[l, r\] 每个数加上一个 k，就是 p l + = k , p r + 1 − = k p\_\{l\}+=k, p\_\{r+1\}-=k pl\+=k,pr\+1−=k，最后做一遍前缀和。

就是对这个差分数列 p i p\_\{i\} pi做一遍前缀和就得到了原来的数列 a i a\_\{i\} ai,即 a i a\_\{i\} ai 相当于 p \[ 1 , i \] p\_\{\[1,i\]\} p\[1,i\] 这个前缀和。

# 二维前缀和 #

一维的前缀和理解起来和实现起来很简单，二维前缀和的思路也是一样的，比如一个二维数组a,p\[i\]\[j\]就表示a数组从(1,1)坐标到(i,j)所表示的矩形范围内的数据的和。  
p\[i\]\[j\] = p\[i-1\]\[j\]+p\[i\]\[j-1\]-p\[i-1\]\[j-1\]+a\[i\]\[j\]

二维数组前缀和随机一个矩形的和的表示跟一维的数组前缀和稍有不同，比如(a,b)到(c,d)表示的矩形范围的和应该是p\[c,d\]-p\[a-1\]\[\[b\]-p\[a,b-1\]+p\[a-1\]\[b-1\]，至于为什么是这么算，自己画一个矩阵模拟一下其实很容易理解的，我的参考博客中是有图的，可以参考那个。

# 二维差分 #

二维差分的思路与一维差分基本一致，对于二维数组a，p\[i\]\[j\]=a\[i\]\[j\]-a\[i-1\]\[j\]-a\[i\]\[j-1\]+a\[i-1\]\[j-1\]，p就是二维数组a的差分数组。

二维差分数组单独使用也是有意义的，比如将原数组看做是一个二维前缀和数组，它可以维护多次对一个矩形区域加上一个数，。譬如使 \[(a,b), (c,d)\] 每个数加上一个 k，就是

p[a][b]+=k;
    p[c+1][d]-=k;
    p[c][d+1]-=k;
    p[c+1][d+1]+=k;

至于算法的过程还是可以画图模拟一下。

# 例题 #

题目地址[J Matrix Subtraction][]  
题意：给一个二维矩阵大小为n*m，给一个子矩阵大小a*b,每次操作一个子矩阵，给子矩阵上每一个值减一，问能不能使得最后的大矩阵的值全部为0。  
思路：我们直接 n 2 n^2 n2暴力枚举a\*b的子矩阵，每一块都减去**当前值**使之变为 0，利用二维差分可以快速实现这个操作。如果中途出现了负数或最后不全为 0，则输出 QAQ。

#include <bits/stdc++.h>
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <algorithm>
    //#include <vector>
    //#include <map>
    //#include <stack>
    //#include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1004;
    int mm[N][N],k[N][N];
    void add(int i,int j,int a,int b,int z)
    { 
        mm[i][j]+=z;
        mm[i+a][j]-=z;
        mm[i][j+b]-=z;
        mm[i+a][j+b]+=z;
    }
    bool check(int n,int m)
    { 
        for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                if(mm[i][j]!=0)
                { 
                    return false;
                }
            }
        }
        return true;
    }
    void solve()
    { 
    	int n,m,a,b;
    	scanf("%d%d%d%d",&n,&m,&a,&b);
    	for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                scanf("%d",&k[i][j]);
                mm[i][j]=k[i][j]+k[i-1][j-1]-k[i][j-1]-k[i-1][j];
            }
        }
        int f = 0;
        for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                mm[i][j]+=mm[i-1][j]+mm[i][j-1]-mm[i-1][j-1];//求前缀和
                if(mm[i][j] < 0)    //如果前面处理过后的二维数组有一个负数，就说明不能达到要求，如果继续计算的话，会将这个负数加到0，然而对子矩阵的操作只能是减一，而不能加数字，因而出现负数必然是不对的
                { 
                    f = 1;
                    break;
                }
                if(i+a-1>n||j+b-1>m)
                { 
                    break;
                }
                add(i,j,a,b,-mm[i][j]);
            }
            if(f)
            { 
                break;
            }
        }
        if(f)
        { 
            puts("QAQ");
        }
        else
        { 
            if(check(n,m))
            { 
                puts("^_^");
            }
            else
            { 
                puts("QAQ");
            }
        }
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[Link 1]: https://www.cnblogs.com/LMCC1108/p/10753451.html
[2]: https://blog.csdn.net/justidle/article/details/104506724
[J Matrix Subtraction]: https://ac.nowcoder.com/acm/contest/7501/J