赞
踩
差分可以用来区间增加,注意询问时需要累加前缀和,因此如果是大量询问,需要他们有序或可以离线。
例题: 6292. 子矩阵元素加 1
这题数据出的,卡一维树状数组;不卡一维差分和二维树状数组。
class Diff2D: """二维差分模板""" def __init__(self,g): self.m,self.n = len(g),len(g[0]) self.mat = [[0]*(self.n+1)]+[[0]+r for r in g] self.diff = [[0]*(self.n+1) for _ in range(self.m+1)] def add(self,x1,y1,x2,y2,v): x2 += 1 y2 += 1 self.diff[x1][y1] += v self.diff[x2][y1] -= v self.diff[x1][y2] -= v self.diff[x2][y2] += v def update(self): mat = self.mat d = self.diff for i,row in enumerate(d[:-1]): for j,v in enumerate(row[:-1]): mat[i+1][j+1] = v - mat[i][j] + mat[i+1][j] + mat[i][j+1] return [r[1:] for r in mat[1:]] class Solution: def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]: grid = [[0] * n for _ in range(n)] g = Diff2D(grid) for x1, y1, x2, y2 in queries: g.add(x1, y1, x2, y2 , 1) return g.update()
例题: 6292. 子矩阵元素加 1
还是前边那道题,但一般不会这么用。
更多的题可能是边更新边累加的,但不会再查询或者更新更前边的数。
class Diff: def __init__(self,a): self.n = len(a) self.a = a[:] self.diff =diff= [a[0]] + [0]*self.n for i in range(1,self.n): diff[i] = a[i] - a[i-1] def add(self,l,r,v): self.diff[l] += v self.diff[r+1] -= v def update(self): return list(accumulate(self.diff[:-1])) class Solution: def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]: d = [Diff([0]*n) for _ in range(n)] for x1, y1, x2, y2 in queries: for i in range(x1,x2+1): d[i].add(y1,y2,1) return [x.update() for x in d]
例题: 2132. 用邮票贴满网格图
class PreSum2d: # 二维前缀和(支持加法和异或),只能离线使用,用n*m时间预处理,用O1查询子矩阵的和;op=0是加法,op=1是异或 def __init__(self,g,op=0): m,n = len(g),len(g[0]) self.op = op self.p=p=[[0]*(n+1) for _ in range(m+1)] if op == 0: for i in range(m): for j in range(n): p[i+1][j+1] = p[i][j+1]+p[i+1][j]-p[i][j]+g[i][j] elif op==1: for i in range(m): for j in range(n): p[i+1][j+1] = p[i][j+1]^p[i+1][j]^p[i][j]^g[i][j] # O(1)时间查询闭区间左上(a,b),右下(c,d)矩形部分的数字和。 def sum_square(self,a,b,c,d): if self.op == 0: return self.p[c+1][d+1]+self.p[a][b]-self.p[a][d+1]-self.p[c+1][b] elif self.op==1: return self.p[c+1][d+1]^self.p[a][b]^self.p[a][d+1]^self.p[c+1][b] class Diff2D: """二维差分模板""" def __init__(self,g): self.m,self.n = len(g),len(g[0]) self.mat = [[0]*(self.n+1)]+[[0]+r for r in g] self.diff = [[0]*(self.n+1) for _ in range(self.m+1)] def add(self,x1,y1,x2,y2,v): x2 += 1 y2 += 1 self.diff[x1][y1] += v self.diff[x2][y1] -= v self.diff[x1][y2] -= v self.diff[x2][y2] += v def update(self): mat = self.mat d = self.diff for i,row in enumerate(d[:-1]): for j,v in enumerate(row[:-1]): mat[i+1][j+1] = v - mat[i][j] + mat[i+1][j] + mat[i][j+1] return [r[1:] for r in mat[1:]] class Solution: def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool: m,n = len(grid),len(grid[0]) p = PreSum2d(grid) # 二维前缀和 d = Diff2D([[0]*n for _ in range(m)]) # 二维差分 # 遍历所有可以贴邮票的位置,并在差分数组里贴上 for i in range(m-stampHeight+1): for j in range(n-stampWidth+1): if p.sum_square(i,j,i+stampHeight-1,j+stampWidth-1) == 0: d.add(i,j,i+stampHeight-1,j+stampWidth-1,1) g = d.update() # 差分数组更新出原数组 # 遍历所有应该贴有票的位置,看看贴了没 for i in range(m): for j in range(n): if grid[i][j] == 0 and g[i][j] == 0: return False return True
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。