差分
前缀和是元素的累加，而差分则是相邻两元素的差；前缀和用来计算整块元素的和，而差分则用来实现整块元素的加或减（例如将a[m]到a[n]都+1）；
同样，差分也可以化区间计算为点计算，减小时间复杂度。
diff[n]的含义，便是原始数组中当前项减去前一项的差。 即： diff[n] = a[n] - a[n-1] ；
主要用于针对某个区间+x的操作复杂度降低，可以o(1)对某个区间增加复杂度，然后可以根据差分数组反推原数组，叫做回收。 其实就是求diff的前缀和 就是回收啦
前缀和知识请参考: 前缀和
有区间更新题目应该考虑差分。
模板
一维差分
定义: diff[n] = a[n] - a[n-1] ；
因此想要[l,r]上+x, 是diff[l]+=x, diff[r+1]-=x，落到diff数组上就是l和r+1
diff数组长度应该n+1，diff[0]=0
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
diff = [0] * (n+1)
for a, b, c in bookings: # [a,b]区间都+c
diff[a - 1] += c
diff[b] -= c
ans = [0] * n
ans[0] = diff[0]
for i in range(1, n):
ans[i] = ans[i - 1] + diff[i]
return ans
差分数组还原成原数组
ans[0] = diff[0]
for i in range(1, n):
ans[i] = ans[i - 1] + diff[i]
二维差分
二维数组diff上某个位置加1会影响当前及右下角方向的点的前缀和计算。
想让矩阵[i,j]到[m,n]整体加x，对差分数组应该有如下操作
diff[i][j] += x (此时求前缀和数组的话从[i,j]一直到右下角都是加了x的）
diff[m + 1][j] -= x, diff[i][n + 1] -= x (此时结果接近正确，只有[m+1,n+1]到右下角都是-x的)
diff[m + 1][n + 1] += x ([m+1,n+1]到右下角都加x，得到正确结果）
模板
# 二维差分矩阵 记录邮票放置情况：
def diffInsert(x1, y1, x2, y2, c=1):
diff[x1][y1] += c # 左上角+1
diff[x1][y2+1] -= c # 右上角右侧位置-1
diff[x2+1][y1] -= c # 左下角下侧位置-1
diff[x2+1][y2+1] += c # 右下角对角处（行列均+1处）+1
二维差分数组的长宽应该是m+2, n+2。
如图，红色部分是(i,j) -> (m,n)。
差分数组还原成原数组: 和计算当前位置前缀和逻辑一样，(i,j)左边+上边的-左上的+(i,j)的，记住要更新diff
# 从二维差分矩阵diff中还原出对应的计数矩阵：运用二维前缀和
for i in range(1, m+1):
for j in range(1, n+1):
diff[i][j] = diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1] + diff[i][j]
Python一维和二维模板
class Diff:
def __init__(self, n):
self.n = n
self.diff = [0] * (n + 1)
# 给[l,r] + val
def add(self, l, r, val):
self.diff[l] += val
self.diff[r + 1] -= val
# 差分数组还原成原数组
def restore(self):
ans = [0] * self.n
ans[0] = self.diff[0]
for i in range(1, self.n):
ans[i] = ans[i - 1] + self.diff[i]
return ans
class Diff2:
def __init__(self, m, n):
self.m = m
self.n = n
self.diff = [[0] * (n + 2) for _ in range(m + 2)]
# 给[x,y] -> [x1,y1] + v
def add_diff(self, x, y, x1, y1, v):
self.diff[x + 1][y + 1] += v
self.diff[x1 + 2][y1 + 2] += v
self.diff[x1 + 2][y + 1] -= v
self.diff[x + 1][y1 + 2] -= v
# 差分数组还原成原数组
def restore(self):
m, n = self.m, self.n
ans = [[0] * n for _ in range(m)]
diff = self.diff
for i in range(1, m + 1):
for j in range(1, n + 1):
# 差分数组还原成原数组: 和计算当前位置前缀和逻辑一样，(i,j)左边+上边的-左上的+(i,j)的，记住要更新diff
diff[i][j] = diff[i][j] + diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
ans[i - 1][j - 1] = diff[i][j]
return ans
应用
一维差分
1109. 航班预订统计 有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
实际上就是区间增加x，然后根据还原出每个点的值。一维差分
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
diff = [0] * (n+1)
for a, b, c in bookings:
diff[a - 1] += c
diff[b] -= c
ans = [0] * n
ans[0] = diff[0]
for i in range(1, n):
ans[i] = ans[i - 1] + diff[i]
return ans
二维差分
2132. 用邮票贴满网格图 给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中, 看能不能贴满，然后无遗漏点的，邮票之间可重合。
class Solution:
def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
m, n = len(grid), len(grid[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
diff = [[0] * (n + 2) for _ in range(m + 2)]
# x range in [0,m)
def get_pre(x, y, x1, y1):
return pre[x1 + 1][y1 + 1] + pre[x][y] - pre[x1 + 1][y] - pre[x][y1 + 1]
# x range in [0,m)
def add_diff(x, y, x1, y1, v):
diff[x + 1][y + 1] += v
diff[x1 + 2][y1 + 2] += v
diff[x1 + 2][y + 1] -= v
diff[x + 1][y1 + 2] -= v
# 遍历grid, 如果为0，则看能不能加邮票，如果能加邮票，就区间加上1, >0表示有邮票覆盖
for i in range(m):
for j in range(n):
pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + grid[i][j]
if grid[i][j] == 1: continue
x, y = i - stampHeight + 1, j - stampWidth + 1
if x >= 0 and y >= 0 and get_pre(x, y, i, j) == 0:
add_diff(x, y, i, j, 1)
# 根据diff还原邮票，如果没被邮票覆盖，并且原来位置需要有邮票，return False
for i in range(1, m + 1):
for j in range(1, n + 1):
diff[i][j] = diff[i][j] + diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
if diff[i][j] == 0 and grid[i - 1][j - 1] == 0:
return False
return True