精华内容
下载资源
问答
  • 一维前缀和 有一串长度为n的数列an,如果要求我们访问**[j,k]**里的数的和。 我们一般的方法是分别求出Sj和Sk的值然后让他们相减。 如果我们了解到前缀和,...二维前缀和 规定:i为行数,j为列数 如果我们想要去求得

    一维前缀和
    有一串长度为n的数列an,如果要求我们访问**[j,k]**里的数的和。
    我们一般的方法是分别求出Sj和Sk的值然后让他们相减。

    如果我们了解到前缀和,我们就可以使用下面这种方法

    	for(int i=1;i<=n;i++) a[i]+=a[i-1];		//a[i]相当于Si(前i项和)
    

    前缀和就是前面i个数的总和
    接下来,我们只需要分别找到a[j-1]a[k],sum=a[k]-a[j-1] (包括a[k]和a[j])

    二维前缀和
    规定:i为行数,j为列数

    如果我们想要去求得a[i][j]的前缀和,
    S[i][j]=S[i-1][j]+S[i][j-1]+S[i-1][j-1];
    求a[2][4]的前缀和 代码如下:

    	#include<iostream>
    
    	using namespace std;
    
    	const int m=10;
    	int a[m][m]; //定义全局变量多余的空自动填充为0 
    
    	void func()
    	{
    	int i,j;
    	for(i=1;i<=5;i++){
    		for(j=1;j<=5;j++) cin>>a[i][j];
    	}
    	for(i=1;i<3;i++){
    		for(j=1;j<5;j++){
    			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    		}
    	}
    	 cout<<a[2][4];
    	}
    	int main()
    	{
    	func();
    	return 0;
    	}
    

    通过二维前缀和求某一矩阵和
    从a[2][2] (左上角) 到 a[3][4] (右下角)

    	 #include<iostream>
    
    	using namespace std;
    
    	const int m=10;
    	int a[m][m];
    
    	void func()
    	{
    	int i,j,ans;
    	for(i=1;i<=5;i++){
    		for(j=1;j<=5;j++) cin>>a[i][j];
    	}
    	for(i=1;i<6;i++){
    		for(j=1;j<6;j++){
    			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    		}
    	}			//该循环实现了每一点都变成了二维前缀和 
    	//已知(x1=2,y1=2) (x2=3,y2=4)	求这两个点构成的矩阵和 
    	//S( 2,2 -> 3,4)=S[3,4]-S[x1-1,y2]-S[x2,y1-1]+S[x1-1,y1-1]
    	ans=a[3][4]-a[1][4]-a[3][1]+a[1][1];
    	cout<<ans; 
    	}
    	int main()
    	{
    	func();
    	return 0;
    	}
    

    1 2 3 4 5
    6 7 8 9 10
    11 12 13 14 15
    16 17 18 19 20
    21 22 23 24 25

    展开全文
  • 二维前缀二维前缀和公式: sum[x2][y2]=b[x2][y2] + sum[x2][y1-1] + sum[x1-1][y2] - sum[x1-1][y1-1] 算法思路:创立数组sum[ ][ ],sum[i][j]表示ij坐标左上角全部数的总和(包括i,j),求x1,y1,x2,y2这个...

    二维前缀和(差分与前缀和的下标都从1开始,避免出现越界)


    题目描述:

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

    数据范围
    1≤n,m≤1000
    1≤q≤200000
    1≤x1≤x2≤n
    1≤y1≤y2≤m
    −1000≤矩阵内元素的值≤1000

    输入样例:
    3 4 3
    1 7 2 4
    3 6 2 8
    2 1 2 3
    1 1 2 2
    2 1 3 4
    1 3 3 4
    输出样例:
    17
    27
    21


    二维前缀和公式:

    sum[x2][y2]=b[x2][y2] + sum[x2][y1-1] + sum[x1-1][y2] - sum[x1-1][y1-1]

    算法思路:创立数组sum[ ][ ],sum[i][j]表示ij坐标左上角全部数的总和(包括i,j),求x1,y1,x2,y2这个区间内的数的和就为sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]


    以下是求sum[i][j]的图解

    在这里插入撒大描述

    +左边区间(红色)的数

    在这里插入图片描述

    +上边区间(黄色)的数

    在这里插入图片描述

    -因为左上角区间(黑色)被加了两次,就需要减掉一次

    在这里插入图片描述

    =整个区间(绿色)内所有数的总和

    在这里插入图片描述

    求x1,y1,x2,y2区间内的数的和就由上路反推即可。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    namespace IO{
        inline LL read(){
            LL o=0,f=1;char c=getchar();
            while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
            while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
            return o*f;
        }
    }using namespace IO;
    const int N=1e3+7,base=1e9;
    int sum[N][N];
    int main(){
        int n,m,q;
        n=read(),m=read(),q=read();
        for(int i=1;i<=n;i++){
            for(int x,j=1;j<=m;j++){
                x=read();
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;//求i,j坐标左上角(包括i,j)所有数的和
            }
        }
        int x1,x2,y1,y2;
        while(q--){
            x1=read(),y1=read(),x2=read(),y2=read();
            printf("%d\n",sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]);//前缀和
        }
        return 0;
    }
    
    

    三维前缀和公式:


    PS : 与二维前缀和思想差不多


    s(x2,y2,z2) = b(x2,y2,z2) + s(x1-1,y2,z2)+s(x2,y1-1,z2) + (x2,y2,z1-1) - s(x1-1,y1-1,z2) - s(x1-1,y2,z1-1) - (x2,y1-1,z1-1) + s(x1-1,y1-1,z1-1)

    展开全文
  • 差分 一维差分 二维差分 差分数组意义 前缀和 一维前缀和 二维前缀和 最大难点在于 二维差分数组的理解 二维差分数组d[x][y] 不是指 a数组中具体某两个值的差值. d数组用于统计二维矩阵值的更新,是我告诉你某...

    差分   一维差分   二维差分   差分数组意义 前缀和   一维前缀和   二维前缀和

    最大难点在于   二维差分数组的理解

    二维差分数组d[x][y]   不是指   a数组中具体某两个值的差值.

    d数组用于统计二维矩阵值的更新,是我告诉你某个子矩阵都要加个p,然后用d数组来让这个子矩阵每个值都加上p的.

    学习需要循序渐进,读者且看文章娓娓道来.

    //一维差分,摘自https://blog.csdn.net/Healer66/article/details/87201014

    //简单验证如下
    a[1],a[2],a[3],a[4],a[5]  a[]为原始数列
    b[1],b[2],b[3],b[4],b[5],b[6] b[]为差分数列
    b[1]=a[1]-0
    b[2]=a[2]-a[1]
    b[3]=a[3]-a[2]
    b[4]=a[4]-a[3]
    b[5]=a[5]-a[4]
    b[6]=0-a[5]
    性质1
    a[1]=b[1]
    a[2]=b[2]+b[1]
    a[3]=b[3]+b[2]+b[1]
    a[4]=b[4]+b[3]+b[2]+b[1]
    a[5]=b[5]+b[4]+b[3]+b[2]+b[1]
    性质2

    L=2,R=4
    a[1],a[2]+1,a[3]+1,a[4]+1,a[5]  a[]+1为原始数列,每个元素+1
    b'[1],b'[2],b'[3],b'[4],b'[5],b'[6] b'[]为新的差分数列
    b'[1]=a[1]-0=b[1]
    b'[2]=(a[2]+1)-a[1]=b[2]+1
    b'[3]=(a[3]+1)-(a[2]+1)=b[3]
    b'[4]=(a[4]+1)-(a[3]+1)=b[4]
    b'[5]=a[5]-(a[4]+1)=b[5]-1
    b'[6]=0-a[5]=b[6]

    //二维差分,摘自https://www.cnblogs.com/LMCC1108/p/10753451.html修改了小错误

     

     

    //以下为二维差分模拟过程     a[i][j]子矩阵(3,3)-(4,4)区间每个元素+1   采用   二维差分数组   进行后续计算

    a[i][j]

    sum[i][j]

     

    sum[i][j]的生成代码如下

    #include <stdio.h>
    #include <string.h>
    #define maxn 10
    int a[maxn][maxn],sum[maxn][maxn],d[maxn][maxn];
    int main(){
        int i,j;
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                a[i][j]=1;//a[i][j]矩阵建立
        memset(sum,0,sizeof(sum));
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];//二维前缀和
        for(i=1;i<=6;i++){
            for(j=1;j<=6;j++)
                printf("%d\t",sum[i][j]);
            printf("\n");
        }
        return 0;
    }

    a[i][j]子矩阵(3,3)-(4,4)区间每个元素+1

    对应的二维差分矩阵d[i][j]

    二维差分矩阵d[i][j]的生成代码如下

    #include <stdio.h>
    #include <string.h>
    #define maxn 10
    int a[maxn][maxn],sum[maxn][maxn],d[maxn][maxn];
    int main(){
        int i,j;
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                a[i][j]=1;//a[i][j]矩阵建立
        memset(d,0,sizeof(d));
        d[3][3]+=1,d[3][4+1]-=1,d[4+1][3]-=1,d[4+1][4+1]+=1;//a[i][j]子矩阵(3,3)-(4,4)区间每个元素+1  二维差分数组建立
        for(i=1;i<=7;i++)
            for(j=1;j<=7;j++)
                d[i][j]+=d[i][j-1]+d[i-1][j]-d[i-1][j-1];//二维差分数组建立
        for(i=1;i<=7;i++){
            for(j=1;j<=7;j++)
                printf("%d\t",d[i][j]);
            printf("\n");
        }
        return 0;
    }

    更新后的a[i][j]矩阵

    由二维差分数组d得到更新的a矩阵代码如下

    #include <stdio.h>
    #include <string.h>
    #define maxn 10
    int a[maxn][maxn],sum[maxn][maxn],d[maxn][maxn];
    int main(){
        int i,j;
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                a[i][j]=1;//a[i][j]矩阵建立
        memset(d,0,sizeof(d));
        d[3][3]+=1,d[3][4+1]-=1,d[4+1][3]-=1,d[4+1][4+1]+=1;//a[i][j]子矩阵(3,3)-(4,4)区间每个元素+1  二维差分数组建立
        for(i=1;i<=7;i++)
            for(j=1;j<=7;j++)
                d[i][j]+=d[i][j-1]+d[i-1][j]-d[i-1][j-1];//二维差分数组建立
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                a[i][j]+=d[i][j];//a[i][j]矩阵的更新
        for(i=1;i<=6;i++){
            for(j=1;j<=6;j++)
                printf("%d\t",a[i][j]);
            printf("\n");
        }
        return 0;
    }

    更新的sum矩阵如下

    由二维差分数组d得到更新的sum矩阵代码如下   2019-8-18 10:42

    #include <stdio.h>
    #include <string.h>
    #define maxn 10
    int a[maxn][maxn],sum[maxn][maxn],d[maxn][maxn];
    int main(){
        int i,j;
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                a[i][j]=1;//a[i][j]矩阵建立
        
        memset(d,0,sizeof(d));
        d[3][3]+=1,d[3][4+1]-=1,d[4+1][3]-=1,d[4+1][4+1]+=1;//a[i][j]子矩阵(3,3)-(4,4)区间每个元素+1  二维差分数组建立
        for(i=1;i<=7;i++)
            for(j=1;j<=7;j++)
                d[i][j]+=d[i][j-1]+d[i-1][j]-d[i-1][j-1];//二维差分数组建立
        
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                a[i][j]+=d[i][j];//a[i][j]矩阵的更新
        
        memset(sum,0,sizeof(sum));
        for(i=1;i<=6;i++)
            for(j=1;j<=6;j++)
                sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];//二维前缀和
        
        for(i=1;i<=6;i++){
            for(j=1;j<=6;j++)
                printf("%d\t",sum[i][j]);
            printf("\n");
        }
        return 0;
    }

    好比写名字,一笔一划是普通算法,敲图章是差分算法.2019-8-18 10:50

    展开全文
  • 二维前缀

    2019-06-22 16:28:06
    二维前缀

    二维前缀和

    在这里插入图片描述

    展开全文
  • 二维差分与二维前缀

    千次阅读 2020-12-14 20:20:30
    二维差分和二维前缀和息息相关 二维前缀和很好定义: 但差分很不直观,要用前缀和的逆运算的特点推 那么假设每个点的差分值是 ci,j ,而我们知道一维差分的前缀和即为当前点的值,那么二维差分也不例外。所以二维...
  • 二维前缀和!

    2020-08-22 23:08:20
    二维前缀和 南昌理工学院ACM集训队 ???? 给你一个二维平面,要求它的区间和,怎么办呢? 正所谓“暴力出奇迹”,我们当然可以枚举每一个区间的数然后相加,但是聪明的孩子就会开始思考,既然一维数组存在区间和的...
  • 【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用

    千次阅读 多人点赞 2021-05-31 09:12:12
    【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用 文章目录【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用在区间范围内统计奇数数目★区域和检索 - 数组不可变★★子数组异或查询★★定长子串中元音的最大数目★★生存...
  • 一维和二维前缀

    2021-01-30 15:30:18
    目录一维前缀和基本思想模板例题二维前缀和基本思想模板例题([原题](https://www.acwing.com/problem/content/798/)) 一维前缀和 基本思想 前缀和是什么呢?前缀就是一个数组的某项下标之前(包括此项元素)的所有...
  • 一维 二维 前缀

    2020-02-04 22:18:08
    一维 二维 前缀和 一维: 略 二维: 模板题入口 #include<bits/stdc++.h> using namespace std; const int N=1010; int a[N][N],s[N][N]; int n,m,k; int main(){ cin>>n>>m>>k; for...
  • 二维前缀和详解

    2019-09-29 00:32:07
    引入 还是先从例题引入,给你一个二维平面,要求在$\Theta(1)$的时间复杂度内求出一个矩形内数的和。 显然,对于极端情况,二维平面退化成一维,那么我么可以用前缀...红色区域所有数的和即为二维前缀和中点$(i,...
  • 前缀和、二维前缀和与差分的小总结

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

    2020-01-17 22:51:34
    文章目录二维前缀和简单总结什么是二维前缀和有啥用?具体实施步骤1 .预处理二维数组(`假设为map[][]`)2.实践求某个矩形/正方形区域内的数字和学以致用题解如下 二维前缀和简单总结 注:这篇博客的两张图是我从...
  • 前缀和&二维前缀

    2019-06-29 10:26:00
    那么,怎样求二维前缀和呢? 二维前缀和: 绿色点的前缀和就是黄色、红色、灰色和绿色的点权和 怎样计算? s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; 绿色部分的前缀和=(红色+灰色)+(黄色+灰色)-...
  • 二维前缀和是一维前缀和在二维上的体现,要想了解清楚二维前缀和,最好先学习一维前缀和,在逐步深入二维前缀和。因此我们先从一维的开始讲起,另外一个容易忽视的点是,前缀和优化的是查询复杂度,而不是总体的...
  • 1.2二维前缀和 2.题目 2.1输入描述: 2.2输出描述: 2.3输入 2.4输出 3.题目理解 3.1思路 4.程序 4.1运行结果 1前缀和 1.1一维前缀和 1.2二维前缀和 求D=(A+B+C+D)-(A+B)-(A+C)+A D=a[x2][y2]-a...
  • 思考:只要求二维前缀和(淹没为1,没有淹没为0)对于每次询问,只需要O(1)的时间。 //二维前缀和 //把s[0][i]和s[i][0]全部置为0 //s[i-1][j-1]加重复了,必须减去。 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,748
精华内容 1,099
关键字:

二维前缀