广州网站排名推广公司,现货交易平台排名,深圳网站制作必荐祥奔科技,阿里巴巴怎么做网站题目链接
【模板】二维差分_牛客题霸_牛客网
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推#xff0c;求职就业一站解决_牛客网
描述
给定一个 nmnm 的整数矩阵 bb#xff0c;矩阵的下标从 11 开始记作 bi,jbi,j。现在需要支持 qq 次操作#xff0c;第 tt 次…题目链接
【模板】二维差分_牛客题霸_牛客网
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推求职就业一站解决_牛客网
描述
给定一个 n×mn×m 的整数矩阵 bb矩阵的下标从 11 开始记作 bi,jbi,j。现在需要支持 qq 次操作第 tt 次操作给定五个整数 x1,y1,x2,y2,kx1,y1,x2,y2,k表示将以左上角 (x1,y1)(x1,y1)、右下角 (x2,y2)(x2,y2) 为边界的子矩阵内的每个元素都增加 kk。全部操作执行完毕后请输出最终矩阵。
【名词解释】 ∙ ∙子矩阵从矩阵中连续选取若干行与若干列得到的矩形区域。
输入描述
在一行上输入三个整数 n,m,q(1≦n,m≦1000; 1≦q≦105)n,m,q(1≦n,m≦1000; 1≦q≦105)依次表示矩阵行数、列数与操作次数。 此后 nn 行第 ii 行输入 mm 个整数 bi,1,bi,2,…,bi,m(−109≦bi,j≦109)bi,1,bi,2,…,bi,m(−109≦bi,j≦109)描述矩阵初始元素。 再之后 qq 行每行输入五个整数 x1,y1,x2,y2,k(1≦x1≦x2≦n; 1≦y1≦y2≦m; −109≦k≦109)x1,y1,x2,y2,k(1≦x1≦x2≦n; 1≦y1≦y2≦m; −109≦k≦109)描述一次矩阵加法操作。
输出描述
输出 nn 行每行 mm 个整数表示所有操作结束后矩阵的最终状态。同行相邻元素之间使用一个空格分隔。
示例 2 3 4
1 2 3
4 5 6
1 1 2 2 3
1 2 2 3 -1
1 1 1 3 4
1 1 2 1 1输出 ;9 8 6
8 7 5
说明
在该样例中
∙ ∙第一次操作将 (1,1)−(2,2)(1,1)−(2,2) 内的四个元素各自增加 3
∙ ∙第二次操作将 (1,2)−(2,3)(1,2)−(2,3) 内的六个元素各自减少 1
∙ ∙第三次操作将 (1,1)−(1,3)(1,1)−(1,3) 内的三个元素各自增加 4
∙ ∙第四次操作将 (1,1)−(2,1)(1,1)−(2,1) 内的两个元素各自增加 1。
最终得到的矩阵如输出所示。
示例2
示例2
输入
3 3 1
0 0 0
0 0 0
0 0 0
1 1 3 3 5
复制
输出
5 5 5
5 5 5
5 5 5
复制
说明
该样例中只进行一次操作将整个矩阵所有元素都增加
5
5
这个问题是典型的二维区间更新问题解题的关键在于高效处理多次子矩阵的增量更新操作。传统方法是每次操作遍历整个子矩阵并逐一更新时间复杂度为 O (nmq)当 n、m、q 很大时会导致超时。这里使用的二维差分技术能将单次操作的时间复杂度优化到 O (1)整体复杂度降为 O (n*m q)。
核心思路 差分矩阵 差分矩阵 d[i][j] 记录原矩阵 matrix 中每个位置的增量变化。通过差分矩阵可以快速对整个子矩阵进行更新而无需遍历每个元素。 初始化差分矩阵 根据原矩阵 matrix 构建差分矩阵 d使得通过前缀和运算可以还原出原矩阵。具体公式为
d 坐标从 1 开始 使用 1-base 坐标
matrix[][] 坐标从0开始 使用0-base 坐标
d[i][j]matrix[i][j] -matrix[i-1][j]-matrxi[i][j-1] matrix[i-1][j-1] 3 . 区间更新优化 每次对子矩阵 (x1, y1) 到 (x2, y2) 增加 k 时只需修改差分矩阵的四个角点 # d 坐标从 1 开始 使用 1-base 坐标
d[x1][y1] k # 左上角 增量开始
d[x21][y1]-k # 左下角 增量结束 列结束
d[x1][y21] -k # 右上角增量结束 行方向这样每次操作的时间复杂度仅为 O (1)。
结果还原 所有操作完成后通过前缀和运算将差分矩阵还原为最终的矩阵
matrix[i][j]d[i][j]matrix[i-1][j]matrix[i][j-1]-matrix[i-1][j-1]# matrix[i-1][j-1] 为matrix[i-1][j]matrix[i][j-1]公共部分加了两次 关键步骤 差分矩阵初始化
d[ [ 0 for _ in range(m2) ] for _ in range(n2) ]for i in range(1,n1):for j in range(1,m1):d[i][j]matrix[i-1][j-1]if i 1:d[i][j]-matrix[i-2][j-1]if j1:d[i][j]-matrix[i-1][j-2]if i 1 and j1 :d[i][j]matrix[i-2][j-2] # 公共部分上面减去两次 加回来 4. 处理区间优化 for i in range(q):x1,y1,x2,y2,kmap(int,input().split())d[x1][y1]k # 开始左上角d[x21][y1]-k # 结束左下角 行结束d[x2][y21] -k # 结束 右上角 列结束d[x21][y21]1 #公共区域减去两次 加回来
5. 还原最终矩阵 for i in range(1,n1):for j in range(1,m1):matrix[i-1][j-1]d[i][j]if i1:matrix[i-1][j-1]-dp[i-2][j-1]if j 1:matrix[i-1][j-1]-dp[i-1][j-2]if i1 and j1:matrix[i-1][j-1]-dp[i-2][j-1]
复杂度分析
时间复杂度初始化 O (nm) 更新操作 O (q) 还原 O (nm) O(n*m q)空间复杂度O (n*m)存储差分矩阵 这种方法在处理大量区间更新时非常高效适用于题目中的数据范围n, m ≤ 1000q ≤ 10^5。
案例
二维差分矩阵的构建原理我们通过一个具体例子来理解它的推导过程。
例子3×3 矩阵
假设原矩阵 matrix 如下
matrix [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]步骤 1明确差分矩阵的定义
差分矩阵 d[i][j] 记录的是原矩阵 matrix 中每个位置的增量变化使得通过前缀和运算可以还原出原矩阵。具体来说
前缀和公式 matrix[i][j] 左上角到(i,j)的所有d值之和 即 python 运行 matrix[i][j] d[1][1] d[1][2] ... d[i][j]步骤 2推导差分矩阵的递推关系
为了满足前缀和公式差分矩阵 d[i][j] 应满足
d[i][j] matrix[i][j] - 上方区域的和 - 左方区域的和 左上角重叠区域的和数学推导 python
运行
d[i][j] matrix[i][j] - (matrix[i-1][j]) - (matrix[i][j-1]) (matrix[i-1][j-1])这里加上 matrix[i-1][j-1] 是因为左上角区域被重复减去了两次。
手动计算差分矩阵
我们来手动计算上面例子的差分矩阵 d
初始化差分矩阵
python
运行
d [[0, 0, 0, 0], # 第0行索引0和第0列索引0为辅助行/列[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0]
]计算 d [1][1]
python
运行
d[1][1] matrix[0][0] 1计算 d [1][2]
python
运行
d[1][2] matrix[0][1] - matrix[0][0] 2 - 1 1计算 d [2][1]
python
运行
d[2][1] matrix[1][0] - matrix[0][0] 4 - 1 3计算 d [2][2]
python
运行
d[2][2] matrix[1][1] - matrix[0][1] - matrix[1][0] matrix[0][0] 5 - 2 - 4 1 0完整差分矩阵
plaintext
d [[0, 0, 0, 0],[0, 1, 1, 1],[0, 3, 0, 0],[0, 3, 0, 0]
]验证前缀和还原
通过差分矩阵 d 的前缀和运算验证能否还原出原矩阵 matrix
还原 matrix [1][1]
matrix[1][1] d[1][1] d[1][2] d[2][1] d[2][2] 1 1 3 0 5 # 正确还原 matrix [2][2]
matrix[2][2] d[1][1] d[1][2] d[1][3] d[2][1] d[2][2] d[2][3] d[3][1] d[3][2] d[3][3] 1 1 1 3 0 0 3 0 0 9 # 正确公式总结
二维差分矩阵的核心公式
d[i][j] matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] matrix[i-1][j-1]这个公式确保了通过前缀和运算可以正确还原原矩阵从而实现高效的区间更新操作。
疑问 d[i][j] 对应matrix[i-1][j-1]
为什么 d[1][1] matrix[0][0] 1 但是按照d[i][j] matrix[i][j] - (matrix[i-1][j]) - (matrix[i][j-1]) (matrix[i-1][j-1]) 应该d[i][j]matrix[1][1]-matrix[0][1]matrix[1][0]matrix[0][0] 0
这里的混淆源于索引系统的转换和边界条件的处理。 关键澄清索引系统转换
你的代码使用了1-based 索引从 1 开始而 Python 列表默认是0-based 索引从 0 开始。这导致 matrix[0][0] 对应原矩阵的第 1 行第 1 列1-basedd[1][1] 对应差分矩阵的第 1 行第 1 列1-based 因此d[1][1] 应直接等于 matrix[0][0]因为它们表示同一个位置。
公式应用的边界条件
差分公式 d[i][j] matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] matrix[i-1][j-1] 在边界处需要特殊处理
当 i1 或 j1 时
matrix[i-1][j] 或 matrix[i][j-1] 可能越界例如 matrix[-1][j]此时越界部分视为 0因为原矩阵的 前一行 或 前一列 不存在
具体例子
对于 d[1][1]1-based python
运行
i 1, j 1 # 对应 matrix[0][0]0-based# 代入公式
d[1][1] matrix[0][0] - matrix[-1][0] - matrix[0][-1] matrix[-1][-1]# 由于 matrix[-1][0] 和 matrix[0][-1] 越界视为 0
d[1][1] matrix[0][0] - 0 - 0 0 matrix[0][0] 1
计算的 d[1][1] 0 是错误的因为 索引混淆你误用了 1-based 索引代入公式 例如你写的 matrix[1][1] 实际对应原矩阵的第 2 行第 2 列值为 5 忽略边界条件当 i1 或 j1 时公式中的越界项需视为 0
正确计算示例 3×3 矩阵例子验证
原矩阵0-based
matrix [[1, 2, 3], # 第0行[4, 5, 6], # 第1行[7, 8, 9] # 第2行
]
差分矩阵初始化1-based
d[1][1] matrix[0][0] 1 # 边界情况直接赋值d[1][2] matrix[0][1] - matrix[0][0] 2 - 1 1
d[2][1] matrix[1][0] - matrix[0][0] 4 - 1 3d[2][2] matrix[1][1] - matrix[0][1] - matrix[1][0] matrix[0][0] 5 - 2 - 4 1 0 完整差分矩阵
d [[0, 0, 0, 0], # 第0行辅助行[0, 1, 1, 1], # 第1行对应原矩阵第0行[0, 3, 0, 0], # 第2行对应原矩阵第1行[0, 3, 0, 0] # 第3行对应原矩阵第2行
]
代码验证
for i in range(1, n 1):for j in range(1, m 1):d[i][j] matrix[i - 1][j - 1] # 对应原矩阵的位置if i 1: # 处理 i 1 的情况d[i][j] - matrix[i - 2][j - 1]if j 1: # 处理 j 1 的情况d[i][j] - matrix[i - 1][j - 2]if i 1 and j 1: # 处理 i 1 且 j 1 的情况d[i][j] matrix[i - 2][j - 2]
总结
索引转换1-based 的 d[i][j] 对应 0-based 的 matrix[i-1][j-1]边界条件当 i1 或 j1 时公式中的越界项视为 0 差分矩阵的初始化确实需要特别注意索引系统的转换和边界条件这是理解二维差分的关键 为什么差分矩阵使用 1-based 索引
差分矩阵 d 的索引从 1 开始主要是为了避免处理边界条件时的复杂判断。具体原因如下 公式简洁性 二维差分的核心公式 d[i][j] matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] matrix[i-1][j-1] 如果使用 0-based 索引当 i0 或 j0 时matrix[i-1][j] 会导致索引越界如 matrix[-1][j]需要额外的条件判断。 2.减少特殊处理 使用 1-based 索引后d[1][1] 对应 matrix[0][0]公式在边界处依然成立。例如
python
运行
d[1][1] matrix[0][0] - matrix[-1][0] - matrix[0][-1] matrix[-1][-1]
# 越界部分视为0因此 d[1][1] matrix[0][0] 代码中的索引对应关系
差分矩阵 d (1-based)原矩阵 matrix (0-based)d[1][1]matrix[0][0]d[1][2]matrix[0][1]d[i][j]matrix[i-1][j-1]
验证代码逻辑
让我们通过你的 3×3 矩阵例子验证 原矩阵0-based
matrix [[1, 2, 3], # 第0行[4, 5, 6], # 第1行[7, 8, 9] # 第2行
]
差分矩阵初始化1-based
d[1][1] matrix[0][0] 1 # 边界情况直接赋值
d[1][2] matrix[0][1] - matrix[0][0] 2 - 1 1
d[2][1] matrix[1][0] - matrix[0][0] 4 - 1 3
d[2][2] matrix[1][1] - matrix[0][1] - matrix[1][0] matrix[0][0] 5 - 2 - 4 1 0
如果使用 0-based 索引会怎样 如果差分矩阵 d 也使用 0-based 索引代码会变得更复杂
# 假设d也使用0-based索引这不是你的代码
d [[0] * m for _ in range(n)]for i in range(n):for j in range(m):d[i][j] matrix[i][j]if i 0:d[i][j] - matrix[i-1][j]if j 0:d[i][j] - matrix[i][j-1]if i 0 and j 0:d[i][j] matrix[i-1][j-1]# 更新操作也需要调整
for _ in range(q):x1, y1, x2, y2, k map(int, input().split())x1 - 1 # 转换为0-basedy1 - 1x2 - 1y2 - 1d[x1][y1] kif x2 1 n:d[x21][y1] - kif y2 1 m:d[x1][y21] - kif x2 1 n and y2 1 m:d[x21][y21] k 可以看到使用 0-based 索引会引入更多边界判断代码更易出错。
总结 索引系统差异 matrix 是 Python 列表使用 0-based 索引d 使用 1-based 索引是为了简化差分公式的实现 优势 避免了 matrix[-1][j] 这种越界情况差分公式在所有位置统一适用无需特殊处理边界
调整差分数组 d[x1][y1] kd[x2 1][y1] - kd[x1][y2 1] - kd[x2 1][y2 1] k
这段代码是二维差分矩阵的区间更新操作核心逻辑让我详细解释它的工作原理
二维差分的区间更新原理 当我们要对原矩阵的子矩阵 (x1,y1) 到 (x2,y2) 全部加上 k 时只需在差分矩阵 d 上修改四个角点
d[x1][y1] k 从 (x1,y1) 开始的所有元素都会因为这个点的增量而增加 k。
d[x21][y1] - k 在 x21 行的 y1 列处减去 k抵消掉从 x21 行开始的多余增量因为我们只需要更新到 x2 行。
d[x1][y21] - k 在 y21 列的 x1 行处减去 k抵消掉从 y21 列开始的多余增量因为我们只需要更新到 y2 列。
d[x21][y21] k 在 (x21, y21) 处加上 k抵消掉前两步重复减去的部分双重抵消。
可视化示例
假设原矩阵是一个全 0 矩阵我们要对左上角 (1,1) 到右下角 (2,2) 的子矩阵加上 3 原矩阵: 差分矩阵d:
0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 0 -3
0 0 0 0 → 0 0 0 0 0
0 0 0 0 0 0 0 0 00 -3 0 0 3
d[1][1] 3从 (1,1) 开始的区域都会被加上 3d[3][1] -3从第 3 行开始的区域会被减去 3抵消d[1][3] -3从第 3 列开始的区域会被减去 3抵消d[3][3] 3右下角 (3,3) 处加 3抵消双重抵消
为什么这样有效 差分矩阵的核心思想是通过前缀和运算还原原矩阵。当我们修改差分数组的某个点时会影响从该点开始的所有前缀和结果。 通过这四个角点的修改我们巧妙地控制了增量的作用范围使得 子矩阵内的每个元素都增加 k 子矩阵外的元素不受影响 这种方法将每次区间更新的时间复杂度从 O (n*m) 优化到 O (1)大大提高了效率。 完整代码 n ,m , q map(int ,input().split())
maxtrix [list(map(int, input().split())) for _ in range(n)]d [[0 for _ in range(m 2)] for _ in range(n 2)]
# 初始化差分数组
for i in range(1, n 1):for j in range(1, m 1):d[i][j] maxtrix[i - 1][j - 1]if i 1:d[i][j] - maxtrix[i - 2][j - 1]if j 1:d[i][j] - maxtrix[i - 1][j - 2]if i 1 and j 1:d[i][j] maxtrix[i - 2][j - 2]
# 处置修改
for _ in range(q):x1, y1, x2, y2, k map(int, input().split())# 调整差分d[x1][y1] kd[x2 1][y1] - kd[x1][y2 1] - kd[x2 1][y2 1] k# 根据差分还原数组
for i in range(1, n 1):for j in range(1, m 1):maxtrix[i - 1][j - 1] d[i][j]if i 1:maxtrix[i - 1][j - 1] maxtrix[i - 2][j - 1]if j 1:maxtrix[i - 1][j - 1] maxtrix[i - 1][j - 2]if i 1 and j 1:maxtrix[i - 1][j - 1] - maxtrix[i - 2][j - 2]for row in maxtrix:print( .join(map(str, row)))
