精华内容
下载资源
问答
  • 前缀和与差分

    2020-04-23 22:38:08
    这里写目录标题图示:公式:前缀和差分:用途:差分例题:题目: [D....分析:AC代码: 图示: a数组是b数组的前缀和 ...前缀和与差分两者互为逆运算 前缀和: a[i]=a[i-1]+b[i] 我们可以得出a[i]就是b数组...

    图示:

    a数组是b数组的前缀和

    b数组是a数组的差分
    在这里插入图片描述

    公式:

    前缀和与差分两者互为逆运算

    前缀和:

    a[i]=a[i-1]+b[i]
    我们可以得出a[i]就是b数组的前i项之和。

    差分:

    b[i]=a[i]-a[i-1]
    我们可以得出b[i]就是a[i]与a[i-1]的差。

    用途:

    前缀和可以将数组区间的求和运算从O(n)级别降低到O(1)级别

    差分可以将一个区间的增加与减少运算从O(n)级别降低到O(1)级别

    差分例题:

    题目: D. Constant Palindrome Sum.

    分析:

    每次判断当前数目可变的区间与变化个数,对区间进行差分运算

    AC代码:

    package C636;
    
    import java.util.*;
    
    public class D {
    	public static void main(String[] args) {
    		Scanner sc=new Scanner(System.in);
    		int t=sc.nextInt();
    		while(t-->0){
    			int n=sc.nextInt(),k=sc.nextInt();
    			int arr[]=new int[n];
    			int c[]=new int[2*k+1];
    			for(int i=0;i<n;i++){
    				arr[i]=sc.nextInt();
    			}
    			for(int i=0;i<n/2;i++){
    				int x=i,y=n-i-1;
    				int min=Math.min(arr[x], arr[y])+1;
    				int max=Math.max(arr[x], arr[y])+k;
    				int mid=arr[x]+arr[y];
    				c[1]+=2;
    				c[min]--;
    				c[mid]--;
    				if(mid!=2*k){
    					c[mid+1]++;
    				}
    				if(max!=2*k){
    					c[max+1]++;
    				}
    			}
    			int ans=2*n;
    			for(int i=1;i<=2*k;i++){
    				c[i]+=c[i-1];
    				ans=Math.min(ans, c[i]);
    			}
    			System.out.println(ans);
    		}
    	}
    }
    
    
    
    展开全文
  • 前缀和、二维前缀和与差分的小总结

    万次阅读 多人点赞 2018-08-17 16:21:35
    在了解二维前缀和之前,我们首先需要了解一下什么是前缀和。 如果我给你一串长度为n的数列a1,a2,a3......an,再给出m个询问,每次询问给出L,R两个数,要求给出区间[L,R]里的数的,你会怎么做,若是没有了解过前缀...

    在了解二维前缀和之前,我们首先需要了解一下什么是前缀和。

    如果我给你一串长度为n的数列a1,a2,a3......an,再给出m个询问,每次询问给出L,R两个数,要求给出区间[L,R]里的数的和,你会怎么做,若是没有了解过前缀和的人看到这道题的想法可能是对于m次询问,我每次都遍历一遍它给的区间,计算出答案,这样子的方法固然没错,但是其时间复杂度达到了O(n*m),如果数据量稍微大一点就有可能超时,而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大节省了运算时间。至于怎么用,请看下面一小段代码

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

    没错,前缀和顾名思义就是前面i个数的总和。数组a在经过这样的操作之后,对于每次的询问,我们只需要计算a[R]-a[L-1]就能得到我们想要的答案了,是不是很简单呢。

    在知道了最简单的前缀和之后,我们再来了解一下什么是差分。

    给你一串长度为n的数列a1,a2,a3......an,要求对a[L]~a[R]进行m次操作:

    操作一:将a[L]~a[R]内的元素都加上P

    操作二:将a[L]~a[R]内的元素都减去P

    最后再给出一个询问求a[L]-a[R]内的元素之和?

    你会怎么做呢?你可能会想,我对于m次操作每次都遍历一遍a[L]~a[R],给区间里的数都加上P或减去P,最后再求一次前缀和就行了。没错,这样子确实也能得出正确答案,但时间复杂度却高达O(M*n),对于1<=n,m<=1e5这个数据范围来说直接就tle了,所以说这个方法不可行。既然这样不行的话,那我们要怎么做才能快速的得到正确答案呢?是的,这个时候我们的差分就该派上用场了,我们新开一个数组b,储存每一次的修改操作,最后求前缀和的时候统计一下就能快速的得到正确答案了,详细请看下面代码。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+9;
    int a[maxn],b[maxn];
    int main(){
    	int i,j,k,n,m,p;
    	cin>>n>>m;
    	for(i=1;i<=n;i++){
    		cin>>a[i];
    	}
    	for(i=1;i<=m;i++){
    		int L,R,t;
    		cin>>t>>L>>R>>p;
    		if(t==1){
    			b[L]+=p;b[R+1]-=p; //仔细想想为什么b[R+1]要减去p 
    		}
    		else{
    			b[L]-=p;b[R+1]+=p;
    		}
    	}
    	int add=0;
    	for(i=1;i<=n;i++){
    		add+=b[i];
    		a[i]+=a[i-1]+add;
    	}
    	int x,y;
    	cin>>x>>y;
    	cout<<a[y]-a[x-1]<<endl;
    }

    相信看到这里,大家已经仔细思考过代码了,为什么操作一时b[R+1]要减去p,很简单,因为操作一我只需对[L,R]区间里的数加p,[R+1,n]这个区间里的数没必要加p,所以需要减掉p。

    差分讲解完毕,接下来我们终于要开始今天的正题——二维前缀和了。

    还是以小问题的形式来讲解二维前缀和吧。

    给定一个n*m大小的矩阵a,有q次询问,每次询问给定x1,y1,x2,y2四个数,求以(x1,y1)为左上角坐标和(x2,y2)为右下角坐标的子矩阵的所有元素和。注意仍然包含左上角和右下角的元素。

    怎么做呢?为了方便你们理解,我画个图吧。

    图画的很丑,希望不要介意。如图所示,按题目要求,我们每次要求的答案就是红色圆圈所在的区域的值(注意,这里的x1,x2表示行,y1,y2表示列),对比上面这张图我们能够发现红色区域的值等于四个区域的值减去(白色区域+黑色区域),再减去(白色区域+蓝色区域),最后因为白色区域被减了两次,我们需要再加回来。所以ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];(注意,此时的a数组代表的是前缀和)。突然想起来还没说怎么求二维前缀和,很简单,看下面代码。

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

    为方便理解贴个图

    假如我想求a[2][4]的前缀和,我得先加上a[1][4]的前缀和,再加上a[2][3]的前缀和,然后这个时候我们发现实际上a[1][3]这个部分我们加了两遍,所以我们需要再减去一遍a[1][3],于是得出公式a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]

    接下来看完整代码吧。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e3+9;
    int a[maxn][maxn];
    int main(){
    	int i,j,k,n,m,q;
    	cin>>n>>m>>q;
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++)
    		cin>>a[i][j];
    	}
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++)
    		a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
    	}
    	for(i=1;i<=q;i++){
    		int x1,y1,x2,y2;
    		cin>>x1>>y1>>x2>>y2;
    		int ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
    		cout<<ans<<endl;
    	}
    }

    是不是感觉很简单呢,哈哈哈哈哈哈哈。

    在学完二维前缀和之后,一些同学可能会有疑问,一维前缀和能用上差分,那么二维前缀和能不能用上差分呢?答案是肯定的。

    那么怎么差分呢?方法是和一维类似的,我们也是需要另开一个数组记录修改操作,最后求前缀和时统计修改操作,只是二维每一次操作需要记录4个位置,一维只需要记录2个位置。具体怎么做,看下面代码吧。

    for(int i=0;i<m;i++){//m是修改操作次数 
    	int x1,y1,x2,y2,p;
    	cin>>x1>>y1>>x2>>y2>>p;
    	b[x1][y1]+=p;b[x2+1][y2+1]+=p;
    	b[x2+1][y1]-=p;b[x1][y2+1]-=p;
    }

    好了,一维前缀和、二维前缀和、差分都说完了,希望看这篇文章的人能够有所收获吧。

    展开全文
  • 前缀和与差分介绍 前缀和 简介 前缀和擅长的是查询区间,若要查询一个长度为n的序列中的长k的子序列前缀和的查询速度是O(1),而不用前缀和的方法的时间复杂度是O(k) 差分 简介 差分主要用来修改区间元素值,若...

    前缀和

    简介
    前缀和擅长的是查询区间和,若要查询一个长度为n的序列中的长k的子序列和,前缀和的查询速度是O(1)O(1),而不用前缀和的方法的时间复杂度是O(k)O(k)

    一维前缀和

    生成方法:

    int n;
    cin>>n;
    int a[n+1],sum[n+1];
    memset(a,0,sizeof(a));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++) {
    	cin>>a[i];
    	sum[i]=sum[i-1]+a[i];
    }
    

    查询方法:

    int l,r;
    cin>>l>>r;
    cout<<sum[r]-sum[l-1];
    

    举个例子:
    输入:
    5 3
    1 1 2 1 2
    3 5
    输出:
    5
    查询原理:

    下标(i) a[i] sum[i] 组成部分
    1 1 1 i=11ai\sum_{i=1}^{1}a_{i}
    2 1 2 i=12ai\sum_{i=1}^{2}a_{i}
    3 2 4 i=13ai\sum_{i=1}^{3}a_{i}
    4 1 5 i=14ai\sum_{i=1}^{4}a_{i}
    5 2 7 i=15ai\sum_{i=1}^{5}a_{i}

    若查询 3 ~ 5 的区间内的和
    则有下方式:
    i=35ai=i=12aii=15ai=5\sum_{i=3}^{5}a_{i}=\sum_{i=1}^{2}a_{i}-\sum_{i=1}^{5}a_{i}=5
    即:
    sum5sum2=5sum_{5}-sum_{2}=5
    一般的,查询 i ~ j (i<j)的区间和等于
    sumjsumi1sum_{j}-sum_{i-1}

    二维前缀和

    生成方法:

    int n,m;
    cin>>n>>m;
    int a[n+1][m+1],sum[n+1][m+1];
    memset(a,0,sizeof(a));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++) {
    		cin>>a[i][j];
    		sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
    	}
    

    查询方法:
    查询从左上角(x1,y1x_{1},y_{1})坐标到右下角(x2,y2x_{2},y_{2})坐标的
    矩形区域(x1x_{1} ~ x2x_{2},y1y_{1} ~ y2y_{2})内的所有数字之和。

    int x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;
    cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
    

    举个例子:
    输入:
    3 3
    0 0 1
    1 1 0
    1 0 1
    2 1 2 3
    输出:
    2
    生成原理:
    假设i=3,j=3i=3,j=3
    sum3,3=sum_{3,3}=
    (1,1)(1,2)(1,3)
    (2,1)(2,2)(2,3)
    (3,1)(3,2)(3,3)

    =a3,3=a_{3,3}
    (1,1)(1,2)(1,3)
    (2,1)(2,2)(2,3)
    (3,1)(3,2)(3,3)
    +sum2,3+sum_{2,3}
    (1,1)(1,2)(1,3)
    (2,1)(2,2)(2,3)
    (3,1)(3,2)(3,3)
    +sum3,2+sum_{3,2}
    (1,1)(1,2)(1,3)
    (2,1)(2,2)(2,3)

    (3,1)(3,2)(3,3)
    sum2,2-sum_{2,2}
    (1,1)(1,2)(1,3)
    (2,1)(2,2)(2,3)
    (3,1)(3,2)(3,3)

    所以sumi,j=ai,j+sumi1,j+sumi,j1sumi1,j1sum_{i,j}=a_{i,j}+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}
    查询原理:
    反向推导
    sumi,j=ai,j+sumi1,j+sumi,j1sumi1,j1sum_{i,j}=a_{i,j}+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}

    i=x1,j=y1x2,y2ai,j=sumx2,y2sumx11,y2sumx2,y11+sumx11,y11\sum_{i=x_{1},j=y_{1}}^{x_{2},y_{2}}a_{i,j}=sum_{x_{2},y_{2}}-sum_{x_{1}-1,y_{2}}-sum_{x_{2},y_{1}-1}+sum_{x_{1}-1,y_{1}-1}

    前缀和例题

    一维

    最大连续子序列
    内存限制:256 MiB
    时间限制:1000 ms
    题目描述
    给定一个长度为N的整数序列ai(1iN)a_{i(1≤i≤N)} ,请你计算长度为 K 的最大连续子序列。
    注意:这里的长度为 K,表示连续子序列的元素个数为 K,这里的最大是指 K 个元素的和最大。
    输入格式
    第一行包含两个整数:N,K。
    接下来的一行,共 N 个整数,表示给定的整数序列。
    输出格式
    一个整数,表示长度为 K 的最大连续子序列的和。
    解题思路
    因为他是连续的,我们就可以寻找第i(K<i≤N)位向前数K位的数字和的最大值,即sumisumiksum_{i}-sum_{i-k}
    部分代码

    int n,k,ans=-2e10,a[1e4+5],sum[1e4+5];
    int main () {
    	cin>>n>>k;
    	for(int i=1;i<=n;i++) {
    		cin>>a[i];
    		b[i]=a[i]+b[i-1];
    	}
    	for(int i=k+1;i<=n;i++) 
    		ans=max(ans,sum[i]-sum[i-k]);
    	cout<<ans;
    	return 0;
    }
    

    二维

    激光炸弹
    内存限制:256 MiB
    时间限制:1000 ms
    题目描述
    一种新型的激光炸弹,可以摧毁一个边长为r的正方形内的所有的目标。现在地图上有n(n<=10000)个目标,用整数xi,yix_{i},y_{i}(其值 在[1,5000])表示目标在地图上的位置,每个目标都有一个价值(viv_{i})。激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的正方形的边必须和x,y轴平行。若目标位于爆破正方形的边上,该目标将不会被摧毁。
    输入格式
    输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示xi,yi,vix_{i},y_{i},v_{i}
    输出格式
    输出文件仅有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。
    解题思路

    1. 预处理:
      a. 用sumi,jsum_{i,j}来存储第 i 行 j 列的价值总和。
      b. 将500050005000*5000的范围缩小,按输入的xi,yix_{i},y_{i}的最大值来确定范围
    2. 使用前缀和:
      a. 从(1,1)(1,1)开始统计k=1,l=1i,jak,l\sum_{k=1,l=1}^{i,j}a_{k,l}的值
      b. 从(r,r)(r,r)处开始寻找,k=ir,l=jri,jak,l\sum_{k=i-r,l=j-r}^{i,j}a_{k,l}的最大值

    部分代码

    scanf("%d %d" ,&n ,&r);
    maxx=r,maxy=r;//优化范围
    while(n--) {
    	scanf("%d %d %d" ,&x ,&y ,&v);
    	sum[x][y]+=v,maxx=max(maxx,x),maxy=max(maxy,y);//统计价值,优化范围
    }
    for(int i=1;i<=maxx;i++) //计算前缀和
    	for(int j=1;j<=maxy;j++)
    		sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    for(int i=r;i<=maxx;i++) //寻找最大值
    	for(int j=r;j<=maxy;j++)
    		ans=max(ans,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);
    printf("%d",ans);
    

    差分

    差分简介

    差分主要用来修改区间元素值,若要使一个长度为n的序列中的长k的子序列元素值同时加减,差分的修改速度是O(1)O(1),而挨个修改的方法的时间复杂度是O(k)O(k)
    生成方法:

    int n;
    cin>>n;
    int a[n+1],dif[n+1];
    memset(a,0,sizeof(a));
    memset(sum,0,sizeof(dif));
    for(int i=1;i<=n;i++) {
    	cin>>a[i];
    	dif[i]=a[i-1]-a[i];
    }
    

    修改方法:

    int l,r,c;
    cin>>l>>r>>c;
    dif[l]+=c,dif[r+1]-=c;
    

    举个例子:
    输入:
    5
    1 2 3 4 5
    2 4 1
    输出:
    1 3 4 5 5
    修改原理:
    修改前

    下标 1 2 3 4 5
    原数组 1 2 3 4 5
    差分数组 1 1 1 1 1

    修改后

    下标 1 2 3 4 5
    原数组 1 3 4 5 5
    差分数组 1 2 1 1 0

    解释:
    dif1dif_{1}除外,一般的difi=ai1aidif_{i}=a_{i-1}-a_{i}。所以,当ai+=ca_{i}+=c时,difi+=c,difi+1=cdif_{i}+=c,dif_{i+1}-=c,即aia_{i}ai1a_{i-1}的差增加ccaia_{i}ai+1a_{i+1}的差减少cc
    类似的,当al+c,al+1+c,,ar+ca_{l}+c,a_{l+1}+c,···,a_{r}+c时,difl+c,difr+1cdif_{l}+c,dif_{r+1}-c,即ala_{l}al1a_{l-1}的差增加ccara_{r}ar+1a_{r+1}的差减少cc
    差分还原:
    在差分数组修改完成后,往往要将其还原成原序列。
    我们求差分数组的前缀和即可还原修改后的数组。
    也可以有这样的等价式:原数组<=>差分数组的前缀和<=>前缀和数组的差分数组

    差分例题

    叠干草
    内存限制:256 MiB
    时间限制:1000 ms
    题目描述
    有 N (为奇数)堆干草,按 1…N 编号,开始时每堆高度都是 0。
    FJ给出 K 条指令,每条指令包含两个用空格隔开的整数,例如 “10 13 ”,表示给 10,11,12,13 这四堆干草分别叠加一捆干草,即高度均增加1。
    FJ想知道,干草堆完后,这 N 堆干草高度的中位数(即干草堆完后并排完序后干草堆中间的干草数量)是多少。
    输入格式
    第 1 行:两个整数,分别是 N 和 K。
    第 2…K+1 行:每行两个整数 A 和 B(1 ≤ A ≤ B ≤ N ),表示一条指令。
    输出格式
    一个整数,表示中位数。
    解题思路
    用差分数组修改,再还原成原数组即可。

    小结

    这次关于前缀和与差分介绍就到此结束。前缀和与差分,是一种辅助工具,请大家好好理解运用。

    展开全文
  • 前缀和与差分小结

    2021-01-16 16:05:49
    前缀和与差分小结前缀和一维数组二维数组差分一维数组二维数组 前缀和 一维数组 前缀和其实就相当于数列中的前n项,在m次询问求某个子序列的时,如果每次都遍历序列,则时间复杂度为O(n*m),而若先统计前缀和,...

    前缀和

    一维数组

    前缀和其实就相当于数列中的前n项和,在m次询问求某个子序列的和时,如果每次都遍历序列,则时间复杂度为O(n*m),而若先统计前缀和,则时间复杂度为O(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 -- ){//m次询问
            int l, r;
            cin >> l >> r ;
            cout << s[r] - s[l - 1] << endl;//输出[l,r]区间的和
        }
    

    二维数组

    如上为对于一维数组,而对于二维数组/矩阵,同样可以采用前缀和方法,可进行类比。考虑这样一个问题,对于一个n*m的矩阵,给出q个询问,每次计算(x1, y1), (x2, y2)内的子矩阵和

    #include <iostream>
    using namespace std;
    const int N = 1010;
    int a[N][N], s[N][N];
    int main(){
        int n, m, q;
        cin >> n >> m >> q;
        for(int i = 1; i <= n; i ++ )
           for(int j = 1; j <= m; j ++ ){
               //边输入边计算前缀和
               scanf("%d", &a[i][j]);
               s[i][j] = a[i][j] + s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
           }
        while(q -- ){
            int x1, y1, x2, 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;
    }
    

    如上,关键在于计算前缀和与输出子矩阵和,这里体现了容斥原理的思想,也类似概率论课程中求概率分布的过程(只是这里求的是离散值)。
    tips:在用前缀和或差分法求解问题时,矩阵下标从1开始,这是为了方便计算,下标为0的元素自动初始化为0。

    差分

    一维数组

    差分其实类似于前缀和的逆运算,可以由差分数组的前缀和求出原数组的元素。什么时候运用差分的思想与性质可以减少时间复杂度呢,考虑这样一个问题,对一个长度为n的整数序列,输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c,然后输出进行完所有操作后的序列。
    对数组[l, r]区间上的所有数加上C,其实等价于对其差分数组b进行如下操作:
    B06J_LF1~4R__@J`R3_L.png
    因为差分数组的前缀和为原数组,在位置l上加C相当于对l之后的所有数都加C,因此还需要在r+1位置减去C,从而对数组a的多个数的操作转化为了对其差分数组b中两个数的操作。具体代码如下:

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

    这样,最后只需对差分数组b求和后,即可得原数组a。
    而在刚开始初始化差分数组b时,可以设想刚开始a,b均为0数组,此时一一插入a数组的每个数,即可得到a数组的差分数组b。而该插入操作相当于对特殊区间[i, i]加a[i],如下所示:

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

    完整代码如下:

    #include <iostream>
    using namespace std;
    const int N = 1e5 + 10;
    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]);
        //得到a的差分数组
        for(int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
        while(m -- ){//进行m次操作,转化为对差分数组b的操作
            int l, r, c;
            scanf("%d%d%d", &l, &r, &c);
            insert(l, r, c);
        }
        //由差分数组b求和得到原数组a
        for(int i = 1; i <= n; i ++ ) b[i] = b[i - 1] + b[i];
        for(int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
        return 0;
    }
    

    总结:初始时要得到a的差分数组b也可以利用差分的原始定义,即通过b[1]=a[1], b[2]=a[2]-a[1], b[3]=a[3]-a[2],…得到。通过这种差分的方法,时间复杂度显然减小,n与m的关系由乘积变为加法。

    二维数组

    有了一维数组的基础,二维数组通过类比与画图也可以较好地解决。在对子矩阵的加C操作中,等价于对其差分矩阵做如下操作:
    _SA6H_OA66082H.png

    代码表示如下:

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

    同样在对原始矩阵a求其差分时,设想a矩阵每个元素一一插入:

    insert(i, j, i, j, a[i][j]);
    

    最后,对差分矩阵b进行求前缀和操作,然后输出,完整代码及注释如下:

    #include <iostream>
    using namespace std;
    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);
        //边输入a矩阵边计算其差分矩阵b
        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]);//计算差分矩阵b
          }
        //q次操作
        while(q -- ){
            int x1, y1, x2, y2, c;
            cin >> x1 >> y1 >> x2 >> y2 >> c;
            insert(x1, y1, x2, y2, c);
        }
        //对差分矩阵b求前缀和得到q次操作后的a矩阵
        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];
        //输出
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
            puts(" ");
        }
        
        return 0;
    }
    

    总结:差分思想解题,虽然多开辟了一个数组b,但其减小了时间复杂度,以空间换取了时间。

    寒假复习数据结构与算法,同时刷一些题目,然后刚开始试着写一点题解,请各位大佬指点,共同学习。

    展开全文
  • 前缀和与差分 1.前缀和前缀和是一种预处理,即给出n个数m组访问,如果直接每次都在这些数列上操作,会造成超时,前缀和直接对这些访问进行预处理,最后直接得出取出结果进行计算。即O(n+m)。 相关题目:1046 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,003
精华内容 16,801
关键字:

前缀和与差分