精华内容
下载资源
问答
  • 差分——(2)二维差分

    千次阅读 多人点赞 2020-02-25 23:28:30
    下面我们扩展一下,来介绍二维差分。 什么是二维差分 我们有一个矩阵,如下图所示。 根据二维前缀和表示的是右上角矩形的和,由于差分只涉及前面相邻的数(由一维可以推出),并且由前面范围的数相加得到这个...

    前面部分我们介绍了一维差分,https://blog.csdn.net/justidle/article/details/103761632。下面我们扩展一下,来介绍二维差分。

    什么是二维差分

    我们有一个矩阵,如下图所示。

    根据二维前缀和表示的是右上角矩形的和,由于差分只涉及前面相邻的数(由一维可以推出),并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分,可以简单推测出二维差分的公式

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

    如何从差分矩阵得到原矩阵呢?可以参考下面公式

    p[i][j]=p[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1]; a[i][j]=p[i][j];

    P.S. 道歉,前面这个公式写错了,感谢 @繁星-落眼 的纠正。再次道歉。

    举例

    比如,我们有一个矩阵 a,如下所示:

    1 2 4 3
    5 1 2 4
    6 3 5 9

    那么对应的二维差分矩阵 p 如下:

    1  1  2 -1
    4 -5 -1  3
    1  1  1  2

    应用

     如果我们要在左上角是 (x1,y1),右下角是 (x2,y2) 的矩形区间每个值都 +a,如下图所示

    在我们要的区间开始位置(x1,y1)处 +c,根据前缀和的性质,那么它影响的就是整个黄色部分,多影响了两个蓝色部分,所以在两个蓝色部分 -c 消除 +c 的影响,而两个蓝色部分重叠的绿色部分多了个 -c 的影响,所以绿色部分 +c 消除影响。所以对应的计算方法如下:

    diff[x1][y1] += c;
    diff[x1][y2+1] -=c;
    diff[x2+1][y1] -=c;
    diff[x2+1][y2+1] += c;
    

    模板题

    链接

    我的OJ,http://47.110.135.197/problem.php?id=5227

    题目描述

    输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。
    每个操作都要将选中的子矩阵中的每个元素的值加上 c。
    请你将进行完所有操作后的矩阵输出。

    输入

    第一行包含整数 n,m,q。
    接下来 n 行,每行包含 m 个整数,表示整数矩阵。
    接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作。

    输出

    共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

    样例输入

    3 4 3
    1 2 2 1
    3 2 2 1
    1 1 1 1
    1 1 2 2 1
    1 3 2 3 2
    3 1 3 4 1

    样例输出

    2 3 4 1
    4 3 4 1
    2 2 2 2

    数据范围

    1 ≤ n, m ≤ 1000,
    1 ≤ q ≤ 100000,
    1 ≤ x1 ≤ x2 ≤ n,
    1 ≤ y1 ≤ y2 ≤ m,
    −1000 ≤ c ≤ 1000,
    −1000 ≤ 矩阵内元素的值 ≤ 1000

    分析

    这是一个二维差分的模板题。

    数据分析

    下面我们根据样例输入来分析一下,样例输出是如何得到的。

    初始状态的差分数组 diff 为

     1  1 0 -1
     2 -2 0  0
    -2  1 0  1

    第一次操作为 1 1 2 2 1,得到差分数组 diff 变为

     2  1 -1 -1
     2 -2  0  0
    -3  1  1  1

    第二次操作为 1 3 2 3 2,得到差分数组 diff 变为

     2  1  1 -3
     2 -2  0  0
    -3  1 -1  3

    第二次操作为 1 3 2 3 2,得到差分数组 diff 变为

     2  1  1 -3
     2 -2  0  0
    -2  1 -1  3

    最终,我们可以根据差分数组 diff 求出对应的数组。

    数据范围

    从题目中知道,n 的最大值为 1000,因此我们定义数组为 1004。

    数组的每个数范围为 [-1000, 1000],c 的范围为 [-1000, 1000],操作数 q 最大值为 100000。因此我们可以计算出,经过 q 次操作后,最大的数据为 1000+1000*100000 = 10^8+1000,在 int 的表示范围内。同理最小的数据将是 -1000+(-1000*100000)=-10^8-1000,也在 int 的表示范围内。

    AC 代码

    #include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1e3+6;
    const int MAXM = 1e3+6;
    int a[MAXN][MAXM] = {};
    int diff[MAXN][MAXM] = {};
    
    int main() {
        int n,m,q;
        scanf("%d%d%d", &n, &m, &q);
    
        int i, j;
        for (i=1; i<=n; i++) {
            for (j=1; j<=m; j++) {
                scanf("%d", &a[i][j]);
                diff[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
            }
        }
    
        for (i=0; i<q; i++) {
            int x1, y1, x2, y2, c;
            scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
            diff[x1][y1] += c;
            diff[x1][y2+1] -=c;
            diff[x2+1][y1] -=c;
            diff[x2+1][y2+1] += c;
        }
    
        for (i=1; i<=n; i++) {
            for (j=1; j<=m; j++) {
                diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
                printf("%d ", diff[i][j]);
            }
            printf("\n");
        }
    
        return 0;
    }

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

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

    二维差分

    二维差分和二维前缀和息息相关

    二维前缀和很好定义:
    在这里插入图片描述
    但差分很不直观,要用前缀和的逆运算的特点推
    在这里插入图片描述
    在这里插入图片描述
    那么假设每个点的差分值是 ci,j ,而我们知道一维差分的前缀和即为当前点的值,那么二维差分也不例外。所以二维差分的前缀和即为ai,j 。那么从上面这个公式引导下来
    在这里插入图片描述
    那么由差分值推导到前缀和(也就是推导到当前点的值)便也和简单,上面这个公式移一下项即可

    ai,j = ai,j-1 + ai-1,j - ai-1,j-1 + ci,j

    应用

    那么一维差分可以用于区间加减,那么二维差分呢,那当然也是可以的,只不过是一个二维的区间。

    在这里插入图片描述
    在我们要的区间开始位置(x1,y1)处 +x,根据前缀和的性质,那么它影响的就是整个黄色部分,多影响了两个蓝色部分,所以在两个蓝色部分 -x 消除 +x 的影响,而两个蓝色部分重叠的绿色部分多了个 -x 的影响,所以绿色部分 +x 消除影响。所以对应的计算方法如下:

    1.c[x1][y1]+=x
    2.c[x1][y2+1]-=x
    3.c[x2+1][y1]-=x
    4.c[x2+1][y2+1]+=x
    

    有些引用了大佬

    https://blog.csdn.net/justidle/article/details/104506724

    的博客,大家可以去围观。

    展开全文
  • 差分、二维差分、树上差分

    千次阅读 2019-04-19 20:53:49
    维差分: 给你一个数组a[1] ~ a[n],有Q个操作,每一操作给定 l , r , x 表示 [l, r] 区间所有的数都加上 x, 让你求最后a[1] ~ a[n] 最后各自是多少,要求用 O(n) 复杂度 完成。 设定一个差分数组C[] , 对于每一...

    一维差分:

    给你一个数组a[1] ~ a[n],有Q个操作,每一操作给定 l , r , x 表示 [l, r] 区间所有的数都加上 x, 让你求最后a[1] ~ a[n] 最后各自是多少,要求用 O(n) 复杂度 完成。

    设定一个差分数组C[] , 对于每一次操作 c[l] += x , c[r + 1] -= x.   最后对C 做一遍前缀和。C[i] 最后就得到 a[i] 这个数变化了多少。

    a[1] ~ a[n] 最后各自就是  a[i] + C[i].

     

    二维差分:

    和一维差分差不多, 每一次给定 左上角 (x1,y1),右下角 (x2,y1),x

    每次操作  C[x1][y1] += x ,  C[x2 + 1][y2 + 1] += x ,  C[x1][y2 + 1] -= x , C[x2 + 1][y1] -= x;

    然后做一遍二维前缀和。

     

    树上差分:

    思想和一维二维差分一样,只不过最后做和的时候不同。树上差分的做和  C[i] =  C[i] + (其子树的所有节点的C).也就用dfs再跑一次树 求和。

    还有一点值得注意的就是,点权差分和边权差分有些许不同。

    例如都是改变 u, v 这一条链上的。

    点权:每一次 C[u] += val,  C[v] += val , C[lca(u,v)] -= val , C[Fa_LCA(u,v)] -= val.

    边权:C[u] += val , C[v] += val , C[lca(u,v)] -= 2 * val.

    至于为什么会有差异,用手画一画就理解了。

    展开全文
  • AcWing - 差分矩阵(二维差分)

    千次阅读 2019-08-21 08:54:16
    S[x1][y1] += c, S[x2 + 1][y1] -= c, S[x1][y2 + 1] -= c, S[x2 + 1][y2 + 1] += c,这个和一维差分有着异曲同工之妙。 Accepted Code: /* * @Author: lzyws739307453 * @Language: C++ */ #include ...

    题目链接:https://www.acwing.com/problem/content/description/800/
    时/空限制:1s / 64MB

    题目描述

    输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

    每个操作都要将选中的子矩阵中的每个元素的值加上c。

    请你将进行完所有操作后的矩阵输出。

    输入格式

    第一行包含整数n,m,q。

    接下来n行,每行包含m个整数,表示整数矩阵。

    接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。

    输出格式

    共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

    数据范围

    1≤n,m≤1000,
    1≤q≤100000,
    1≤x1≤x2≤n,
    1≤y1≤y2≤m,
    −1000≤c≤1000,
    −1000≤矩阵内元素的值≤1000

    输入样例

    3 4 3
    1 2 2 1
    3 2 2 1
    1 1 1 1
    1 1 2 2 1
    1 3 2 3 2
    3 1 3 4 1

    输出样例

    2 3 4 1
    4 3 4 1
    2 2 2 2

    解题思路

    题意:给你一个矩阵和q次查询,每次查询将以(x1, y1)为左上角,以(x2, y2)为右下角的子矩阵都加上c,求出最后的矩阵。
    思路:给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
    S[x1][y1] += c, S[x2 + 1][y1] -= c, S[x1][y2 + 1] -= c, S[x2 + 1][y2 + 1] += c,这个和一维差分有着异曲同工之妙。

    Accepted Code:

    /* 
     * @Author: lzyws739307453 
     * @Language: C++ 
     */
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1005;
    int spt[MAXN][MAXN], bits[MAXN][MAXN];
    int main() {
        int n, m, q;
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &spt[i][j]);
                bits[i][j] = spt[i][j] - spt[i - 1][j] - spt[i][j - 1] + spt[i - 1][j - 1];//构造差分矩阵
            }
        }
        while (q--) {
            int x1, y1, x2, y2, v;
            scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
            bits[x1][y1] += v;
            bits[x2 + 1][y1] -= v;
            bits[x1][y2 + 1] -= v;
            bits[x2 + 1][y2 + 1] += v;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                bits[i][j] += bits[i][j - 1] + bits[i - 1][j] - bits[i - 1][j - 1];
                printf("%d%c", bits[i][j], "\n "[j != m]);
            }
        }
        return 0;
    }
    展开全文
  • 前缀和和差分前缀和 因为有i-1所以下标要从1开始存 int n=1010,a[maxn]={0},sum[maxn]={0}; //sum[]为前缀和数组 for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i];//也...
  • 2019中山大学ACM校赛:二维前缀和二维差分

    千次阅读 多人点赞 2019-04-21 16:05:31
    这就要用到二维差分这个思想了(差分:反映离散数据的变化,我们的二维数组就是离散的)。 先讲一下流程: 1、根据原数组各元素的变化确定差分数组的值; 2、对差分数组求前缀和; 3、用求完前缀和的差...
  • bzoj2241 打地鼠 暴力&&二维差分

    千次阅读 2016-02-29 21:35:34
    首先这道题目没有二的性质。。。  数据不是很强,O(N^4)暴力就能过呢(实际上由于常数很小就算是极限也能过的。。另外O(N^6)暴力都过了真是太强辣... 实际上,就是一个二维区间修改+单点查询。。然而你写个暴力总不
  • 维差分 有一个n长度的歌单,某聚聚每轮听歌听到k处(含k)结束,现给出m个k,表示听了m轮,问每首歌听过几次——抽象自xdoj1276 思路 暴力模拟解决: 利用循环,将每一轮的k及之前的数都加一,最后输出结果。...
  • 前缀和、二维前缀和与差分的小总结

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

    千次阅读 2020-02-09 21:38:12
    差分,是一种和前缀和相对的策略。 差分概念 对于一个数列 ,我们需要维护的数据是“相邻两个数之差”。这种策略是,令,即相邻两数的差。我们称数列 为数列 的差分数列。 应用 它可以维护多次对序列的一个区间...
  • AcWing - 差分(一维差分)

    千次阅读 2019-08-21 08:54:04
    时/空限制:1s / 64MB 题目描述 输入一个长度为n的整数序列。 接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。 ...请你输出进行完所有操作后的序列。...第行包含n个整数...
  • C++ 二维前缀和与差分

    千次阅读 2019-05-20 11:37:20
    二维前缀和: #include <bits/stdc++.h> using namespace std; int a[1010][1010]; int main(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j...
  • 二维声波传播方程的有限差分模拟

    千次阅读 2019-04-30 10:00:10
    有限差分表示: 其中f(t)表示源函数,我们用Ricker作为激发源。 离散化的二维声波方程 matlab示例 x,z向共201个节点,节点间隔h=8m,时间采样点位400,采样间隔为0.001s。假设声音传播速度为3km/s,激发源在i=100,...
  • 二维方形板热方程的稳态差分有限差分法 该代码旨在解决2D板中的热方程。 使用固定的边界条件“狄利克雷条件”和所有节点的初始温度,可以解决直到达到稳态,并在代码中选择了公差值。 解决后,图形仿真显示为...
  • 双曲型差分二维)数值例子

    千次阅读 2015-12-15 22:39:07
    双曲型差分二维)数值例子   数值解:   精确解:   注释:显示差分格式,隐式格式暂未考虑 // scilab code  //精确解 t =linspace(0,1,100); t = t'; x = linspace(0,1,100); z = cos( ...
  • 有限差分法解二维热传导记录

    千次阅读 2019-07-30 15:18:17
    在对二维Dirichlet边值问题的热传导方程进行求解时,常常被其边值条件所困扰。 事实上,在应用ADI法解方程时,从n层到n+1/2层时,第0行与第J行往往是边值的体现,可以说是初解,当边值为零时,该行可以省去,但当边...
  • 抛物型差分二维—ADI格式)

    千次阅读 2015-12-15 22:37:34
    抛物型差分二维—ADI格式) example : 模拟四方边界 , 上:100°、下:0°、左:75°、右:50°   //getStart.m // simulate function getStart() clc X_INTERVAL = [0 20]; Y_INTERVAL = [0 30]; T = [ 0 ...
  • 【引入】 首先给出一个问题: 给定n个数,再给出m个询问,每个询问给出区间Li,Ri和x,...而使用差分可以O(n)。 要使用差分,首先我们来谈谈前缀和。 【前缀和】 什么是前缀和?前缀和是一个数组的某项下标之前...
  • #coding:utf-8 from mpl_toolkits.mplot3d import axes3d import matplotlib.pyplot as plt import numpy as np import time def createMatrix( m, n): A = np.zeros( (n + 2,m + 2)) Up = np.ones( (m+2,1)) * 1
  • 算法之前缀和与差分代码实现和算法思想分析

    千次阅读 多人点赞 2021-03-26 20:48:01
    一.前缀和 1.一维前缀和 2.二维前缀和 二.差分 1.一维差分 2.二维差分
  • 泊松方程有很多现成的工具可以用,这里主要是为了加深对算法的理解。...程序以下几个子程序 coefficientmatrix(n):计算系数矩阵 网格向右平移半格以后,系数矩阵是一个[(n-1)(n+2)]^2的矩阵。...
  • 差分数的计算方法

    千次阅读 2014-11-05 20:10:57
    差分数(differential box-counting,DBC),可以作为图像表面纹理粗糙程度的度量,因为它有很好的精确性和适用性,而且能满足计算效率和动态特性的要求。   处理流程: 对于一个M*M大小的图像,在三空间中...
  • 动态有限差分matlab程序

    千次阅读 2015-02-25 02:43:04
    reference: ... 网上很多关于一个节点的一动态有限差分matlab程序,但是如果要做多个节点呢(也即是一),
  • 基于MATLAB的有限差分法解决位瞬态导热问题

    千次阅读 多人点赞 2017-01-08 10:05:37
    本程序解决的是应对平板的二维导热问题,可以定义边界温度及平板材料,获得一定时间后的温度云图。它只考虑热传导,没有考虑对流传热及热辐射,自己做个记录吧。 程序代码如下: clc; clear; %% %本文档为...
  • def trans_data_to_pair(self,data,index): contents=[ data[i:i+index] for i in range(0,len(data),index) ] print(contents) return contents
  • 一、二维图形变化之基本知识 本章涉及向量、世界坐标系、用户坐标系、窗口与视区、齐次坐标、二维变换等 。需要掌握的知识点有: 向量、矩阵以及它们的运算 坐标系的概念和坐标系之间的变换齐次坐标的概念二维...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 92,147
精华内容 36,858
关键字:

二维差分