[python刷题模板] 差分

一、 算法&数据结构

1. 描述

差分可以用来区间增加注意询问时需要累加前缀和因此如果是大量询问需要他们有序或可以离线。

• 对原数组a[i],定义diff[i]为a[i]比前一个大多少即diff[i] = a[i]-a[i]特别的diff[0]=a[0]。
• 那么累加diff的前缀sum(0,i)就是a[i]
• 那么如果对原数组一个区间[l,r]同时增加v,对差分来说,[l,r]之间的相对大小不变不用处理,变的是a[i]比a[i-1]多v、a[r+1]比a[r]少v.
  • 即diff[l]+=v,diff[r+1]-=v。
• 另外对应二维前缀和也有二维差分的用法。
• 树状数组的IUPQ模型应用的就是差分思想但是复杂度多一个log有时会卡TLE。优势是支持随机化查询用log的时间查询前缀和。

2. 复杂度分析

1. 查询query, 平均O(1)
2. 更新updateO(1)

3. 常见应用

1. 区间增加单点询问

4. 常用优化

1. diff可以多设置一位或两位这样后边就不特判越界。

二、 模板代码

1. 二维差分模板题

例题: 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()

2. 一维差分模板

例题: 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]

3. 同时使用二维差分和二维前缀和

例题: 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

三、其他

1. 看数据范围可能还是优先考虑用树状数组。

四、更多例题

五、参考链接