数据结构与算法自学笔记（23）- 二维前缀和、二维差分、离散化技巧

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class048的内容，总结了二维前缀和、二维差分和离散化技巧的核心思想和应用。这些技巧是处理二维矩阵问题的重要工具，特别适用于矩形区域的批量查询和修改。

前置知识

在学习二维前缀和与差分之前，需要掌握以下基础知识：

• 一维前缀和与差分的原理
• 矩阵的基本操作
• 容斥原理的理解
• 坐标系统和索引处理

---

048【必备】二维前缀和、二维差分、离散化技巧

核心概念

二维前缀和的基本思想

二维前缀和是一维前缀和在二维空间的扩展：

• 原理：预处理出每个位置到左上角(0,0)的矩形区域和
• 查询优化：任意矩形区域的和查询在O(1)时间内完成
• 核心公式：使用容斥原理计算矩形区域和

二维差分的基本思想

二维差分用于优化矩形区域的批量修改：

• 原理：将矩形区域修改转化为四个关键点的修改
• 适用场景：大量矩形修改操作，最后统一查询
• 实现方式：通过四点修改实现区域增减，最后二维前缀和还原

离散化技巧

离散化用于处理坐标范围过大的问题：

• 核心思想：将大范围坐标映射到小范围数组
• 关键步骤：收集关键坐标、排序去重、建立映射关系
• 应用场景：坐标值很大但关键点有限的问题

---

题目一：二维前缀和模板

问题描述

给定一个二维矩阵matrix，实现一个类来处理以下类型的多次查询：

• 计算其子矩形范围内元素的总和，该子矩形的左上角为(row1, col1)，右下角为(row2, col2)。

测试链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/

核心思想

通过预计算二维前缀和，实现O(1)时间复杂度的矩形区域和查询：

1. 前缀和构建：s[i][j] 存储从左上角(0,0)到右下角(i-1,j-1)的区域和
2. 容斥原理：利用四个矩形的加减关系计算目标区域
3. 边界处理：通过增加一圈0来简化边界判断

算法实现

from typing import List

class NumMatrix:
    """
    通过预计算二维前缀和，实现O(1)时间复杂度的矩形区域和查询。
    核心思想 (Inclusion-Exclusion Principle):
    1. 创建一个比原矩阵行列各大1的前缀和矩阵 `self.s`。
    2. `self.s[i][j]` 存储原矩阵中从左上角 (0,0) 到右下角 (i-1,j-1) 的矩形区域内所有元素的和。
    3. 构建公式: s[i][j] = matrix[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
       (当前格子的值 + 上方矩形和 + 左方矩形和 - 左上方被重复计算的矩形和)
    4. 查询 (r1,c1)到(r2,c2)的区域和:
       ans = s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1]
       (大矩形 - 上方多余矩形 - 左方多余矩形 + 左上方被重复减去的矩形)
    """
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.s = [[0]]
            return
            
        n = len(matrix)
        m = len(matrix[0])
        # s 的行列都比原 matrix 大 1，方便处理边界
        self.s = [[0] * (m + 1) for _ in range(n + 1)]
        
        # 构建前缀和矩阵，在左边上边和左上补0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                self.s[i][j] = matrix[i - 1][j - 1] + self.s[i - 1][j] + self.s[i][j - 1] - self.s[i - 1][j - 1]

    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        # 传入的r1, c1, r2, c2是0-indexed, 对应到前缀和矩阵需要+1
        r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1
        return self.s[r2][c2] - self.s[r1 - 1][c2] - self.s[r2][c1 - 1] + self.s[r1 - 1][c1 - 1]

容斥原理图解

查询矩形区域 (r1,c1) 到 (r2,c2) 的和：
目标区域 = 大矩形 - 上方矩形 - 左方矩形 + 重叠矩形

    (0,0) ----- (0,c1)----- (0,c2)
      |    A     |      B    |
      |          |           |
   (r1,0) ---- (r1,c1) ---- (r1,c2)
      |    C     |      D    |
      |          |           |
   (r2,0) ---- (r2,c1) ---- (r2,c2)


答案 = (A+B+C+D) - (A+B) - (A+C) + A = D
即：s[r2][c2] - s[r1-1][c2] - s[r2][c1-1] + s[r1-1][c1-1]

算法分析

• 预处理时间复杂度：O(n×m)
• 查询时间复杂度：O(1)
• 空间复杂度：O(n×m)

---

题目二：边框为1的最大正方形

问题描述

给你一个由若干0和1组成的二维网格grid，请你找出边界全部由1组成的最大正方形子网格，并返回该子网格中的元素数量。如果不存在，则返回0。

测试链接：https://leetcode.cn/problems/largest-1-bordered-square/

核心思想

利用二维前缀和快速验证正方形边框是否全为1：

1. 边框验证：边框和 = 整个正方形和 - 内部正方形和
2. 边框元素数量：边长为k的正方形边框有4×(k-1)个元素
3. 枚举优化：从已知最大边长+1开始尝试，进行剪枝

算法实现

class Solution:
    # 打败比例不高，但完全是常数时间的问题
    # 时间复杂度O(n * m * min(n,m))，额外空间复杂度O(1)，因为直接复用的自己
    # 复杂度指标上绝对是最优解
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        """
        核心思想:
        1. 使用二维前缀和快速计算任意子矩阵的元素和。
           为了节省空间，直接在原输入 `grid` 上构建前缀和矩阵。
        2. 遍历所有可能的正方形。一个正方形由其左上角 `(r1, c1)` 和边长 `k` 决定。
        3. 对于一个边长为 `k` 的正方形，其右下角为 `(r2, c2)`。
           要判断其边框是否全为1，可以计算边框上所有元素的和。
           边框和 = (整个正方形的和) - (去掉边框后的内部小正方形的和)
        4. 一个边长为 `k` 的正方形，其边框共有 `4 * (k - 1)` 个单元格 (如果k>1)。
        5. 如果计算出的 "边框和" 等于 `4 * (k - 1)`，则说明这个正方形边框全为1，
           我们更新找到的最大边长。
        6. 从大到小或从小到大遍历边长均可，这里是从小到大。
        """
        n = len(grid)
        m = len(grid[0])
        
        # 直接在 grid 上构建前缀和矩阵
        self._build(n, m, grid)
        
        # 找到的最大合法正方形的边长
        ans = 0
        # 检查是否存在至少一个 1
        if self._sum(grid, 0, 0, n - 1, m - 1) > 0:
            ans = 1

        for r1 in range(n):
            for c1 in range(m):
                # (r1, c1) 作为所有可能的左上角点
                # k 是当前尝试的边长
                # 从已知的最大边长+1开始尝试，进行剪枝
                k = ans + 1
                while r1 + k - 1 < n and c1 + k - 1 < m:
                    r2 = r1 + k - 1
                    c2 = c1 + k - 1
                    
                    # 边框和 = 大正方形和 - 小正方形和
                    border_sum = self._sum(grid, r1, c1, r2, c2) - self._sum(grid, r1 + 1, c1 + 1, r2 - 1, c2 - 1)
                    
                    # 边长为k的正方形，边框有 4 * (k-1) 个格子，可以带入前缀和公式逐个元素相加得到下面成立
                    if border_sum == (k - 1) * 4:
                        ans = k
                    k += 1
        
        return ans * ans

    def _build(self, n, m, g):
        """把g变成原始二维数组的前缀和数组sum，复用自己"""
        for i in range(n):
            for j in range(m):
                g[i][j] += self._get(g, i, j - 1) + self._get(g, i - 1, j) - self._get(g, i - 1, j - 1)

    def _sum(self, g, r1, c1, r2, c2):
        """计算 (r1,c1) 到 (r2,c2) 矩形区域的和"""
        if r1 > r2 or c1 > c2:
            return 0
        return self._get(g, r2, c2) - self._get(g, r2, c1 - 1) - self._get(g, r1 - 1, c2) + self._get(g, r1 - 1, c1 - 1)

    def _get(self, g, i, j):
        """安全地获取前缀和，处理边界情况"""
        return g[i][j] if i >= 0 and j >= 0 else 0

算法分析

• 时间复杂度：O(n×m×min(n,m))
• 空间复杂度：O(1)（复用输入数组）
• 优化策略：剪枝搜索，从大边长开始尝试

---

题目三：二维差分模板

问题描述

给定一个n×n的矩阵，初始时所有元素都是0。进行q次操作，每次操作给定一个矩形区域(r1,c1)到(r2,c2)，将该区域内所有元素加1。求所有操作完成后的矩阵。

测试链接：https://www.luogu.cn/problem/P3397

核心思想

使用二维差分数组优化矩形区域的批量修改：

1. 四点修改：对矩形区域的修改转化为四个关键点的修改
2. 差分还原：通过二维前缀和从差分数组还原最终结果
3. 边界处理：使用额外的边界空间简化边界判断

关键函数解析

def add(r1, c1, r2, c2, k):
    """
    在二维差分矩阵上进行修改，以实现对原矩阵的矩形区域加值。
    这是通过在矩形的四个角点进行修改来完成的。
    
    数学原理：
    要让矩形区域(r1,c1)到(r2,c2)都增加k，需要：
    - 在(r1,c1)处 +k：影响从该点到右下角的所有区域
    - 在(r2+1,c1)处 -k：抵消下方区域的影响
    - 在(r1,c2+1)处 -k：抵消右方区域的影响  
    - 在(r2+1,c2+1)处 +k：补偿被重复抵消的右下角区域
    """
    diff[r1][c1] += k
    diff[r2 + 1][c1] -= k
    diff[r1][c2 + 1] -= k
    diff[r2 + 1][c2 + 1] += k

def build():
    """
    通过一次二维前缀和运算，从差分矩阵还原出最终的矩阵。
    """
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]

二维差分图解

原始矩形修改：对区域(r1,c1)到(r2,c2)加k

(r1,c1) -------- (r1,c2+1)
   |        目标区域    |
   |                   |
(r2+1,c1) ---- (r2+1,c2+1)

四点修改：
diff[r1][c1] += k        (左上角)
diff[r2+1][c1] -= k      (左下角)
diff[r1][c2+1] -= k      (右上角)
diff[r2+1][c2+1] += k    (右下角)

前缀和还原后，只有目标区域内的值增加k

完整实现

import sys

MAXN = 1002
diff = [[0] * MAXN for _ in range(MAXN)]
n, q = 0, 0

def add(r1, c1, r2, c2, k):
    """在二维差分矩阵上进行修改"""
    diff[r1][c1] += k
    diff[r2 + 1][c1] -= k
    diff[r1][c2 + 1] -= k
    diff[r2 + 1][c2 + 1] += k

def build():
    """从差分矩阵还原出最终矩阵"""
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]

def clear():
    """清空差分矩阵"""
    for i in range(1, n + 2):
        for j in range(1, n + 2):
            diff[i][j] = 0

def main():
    """
    核心思想：二维差分数组
    1. 对一个矩阵的子矩阵`(r1,c1)`到`(r2,c2)`范围内的所有元素加`k`，
       如果暴力修改，效率很低。
    2. 我们可以使用一个差分矩阵`D`。对上述范围的修改，只需在`D`的4个点上操作。
    3. 在处理完所有`q`个操作后，对差分矩阵`D`求一次二维前缀和，
       就可以得到最终的矩阵。
    """
    global n, q
    lines = sys.stdin.readlines()
    if not lines:
        return
    
    line_iter = iter(lines)
    
    try:
        while True:
            n_q_line = next(line_iter)
            if not n_q_line: break
            
            n, q = map(int, n_q_line.strip().split())
            clear()
            
            for _ in range(q):
                r1, c1, r2, c2 = map(int, next(line_iter).strip().split())
                add(r1, c1, r2, c2, 1)
            
            build()
            
            # 打印结果
            for i in range(1, n + 1):
                print(' '.join(map(str, diff[i][1:n+1])))
                
    except StopIteration:
        pass

if __name__ == "__main__":
    main()

算法分析

• 时间复杂度：O(q + n²)
• 空间复杂度：O(n²)
• 核心优势：将每次O(n²)的区域修改优化为O(1)的四点修改

---

题目四：用邮票贴满网格图

问题描述

给你一个m×n的二进制矩阵grid，每个格子要么为0（空）要么为1（被占据）。给你邮票的尺寸为stampHeight×stampWidth。要求用邮票覆盖所有空格子，不覆盖任何被占据的格子。邮票可以相互重叠，但不允许旋转，必须完全在矩阵内。

测试链接：https://leetcode.cn/problems/stamping-the-grid/

核心思想

分两步解决：找出所有可贴位置，然后验证覆盖完整性：

1. 可贴位置检测：使用二维前缀和快速判断区域是否全为0
2. 覆盖标记：使用二维差分标记所有被邮票覆盖的位置
3. 完整性验证：检查所有空格子是否都被覆盖

算法实现

class Solution:
    def possibleToStamp(self, grid: List[List[int]], h: int, w: int) -> bool:
        """
        核心思想：分两步走
        1. 找出所有可以贴邮票的位置：
           - 对原 `grid` 建立一个二维前缀和数组 `s`，这样可以 O(1) 查询任何矩形区域的和。
           - 遍历所有可能的邮票左上角 `(r, c)`，利用前缀和 `s` 检查对应的 `h x w` 区域
             是否全为0 (即区域和为0)。
        2. 标记所有被邮票覆盖的空格子：
           - 创建一个二维差分数组 `diff`。
           - 对于第一步中找到的每一个可以贴邮票的区域，我们在 `diff` 数组上执行一次
             范围增加 `+1` 的操作。
           - 所有可贴位置都处理完后，对 `diff` 数组求一次二维前缀和。
             这样 `diff[r][c]` 的值就代表了 `(r, c)` 这个格子被多少张邮票覆盖了。
        3. 验证结果：
           - 遍历原 `grid`，如果发现任何一个空格子 (`grid[r][c] == 0`)
             在 `diff` 数组中对应的值也为0，说明这个空格子没有被任何邮票覆盖，
             因此无法完成任务，返回 `False`。
           - 如果所有空格子都被覆盖了，返回 `True`。
        """
        n = len(grid)
        m = len(grid[0])
        
        # 1. 构建 grid 的前缀和数组
        s = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n):
            for j in range(m):
                s[i + 1][j + 1] = grid[i][j]
        self._build(s)
        
        # 2. 创建差分数组并标记所有可贴邮票的区域
        diff = [[0] * (m + 2) for _ in range(n + 2)]
        for r1 in range(1, n - h + 2):
            for c1 in range(1, m - w + 2):
                r2, c2 = r1 + h - 1, c1 + w - 1
                # 如果 h x w 区域全为0，则可以贴邮票
                if self._sum_region(s, r1, c1, r2, c2) == 0:
                    self._add(diff, r1, c1, r2, c2)
        
        # 3. 从差分数组构建覆盖矩阵
        self._build(diff)
        
        # 4. 验证所有空格子是否都被覆盖
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0 and diff[i + 1][j + 1] == 0:
                    return False
        
        return True

    def _build(self, mat: List[List[int]]):
        """对矩阵构建二维前缀和"""
        n = len(mat)
        m = len(mat[0])
        for i in range(1, n):
            for j in range(1, m):
                mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1]

    def _sum_region(self, s: List[List[int]], r1: int, c1: int, r2: int, c2: int) -> int:
        """查询区域和"""
        return s[r2][c2] - s[r2][c1 - 1] - s[r1 - 1][c2] + s[r1 - 1][c1 - 1]

    def _add(self, diff: List[List[int]], r1: int, c1: int, r2: int, c2: int):
        """二维差分操作"""
        diff[r1][c1] += 1
        diff[r2 + 1][c2 + 1] += 1
        diff[r2 + 1][c1] -= 1
        diff[r1][c2 + 1] -= 1

算法分析

• 时间复杂度：O(n×m)
• 空间复杂度：O(n×m)
• 核心技巧：前缀和检测 + 差分标记

---

题目五：最强祝福力场（离散化技巧）

问题描述

小扣发现了带有「祝福」效果的力场，每个力场覆盖以坐标(x,y)为中心、边长为side的正方形区域。求力场强度最强处的力场强度（即覆盖该点的力场数量的最大值）。

测试链接：https://leetcode.cn/problems/xepqZ5/

核心思想

使用离散化技巧处理大坐标范围问题：

1. 坐标收集：收集所有力场的边界坐标
2. 坐标压缩：排序去重得到压缩坐标轴
3. 映射转换：将原始坐标映射到压缩空间
4. 差分处理：在压缩空间中进行二维差分操作

离散化原理

# 离散化的核心步骤：
# 1. 收集关键坐标
coordinates = []
for field in fields:
    x, y, side = field
    coordinates.extend([x-side//2, x+side//2+1])  # 边界坐标

# 2. 排序去重
coordinates = sorted(list(set(coordinates)))

# 3. 建立映射关系
def get_index(val):
    return bisect.bisect_left(coordinates, val)

# 4. 在压缩空间中操作
compressed_index = get_index(original_coordinate)

算法实现

import bisect
from typing import List

class Solution:
    def fieldOfGreatestBlessing(self, fields: List[List[int]]) -> int:
        """
        核心思想：坐标压缩 + 二维差分
        1. 坐标范围可能很大，无法直接建立网格。但起决定性作用的只有力场的边界。
           因此，我们先进行"坐标压缩"（或称"离散化"）。
        2. 收集所有力场正方形的左右边界和上下边界。
        3. 对收集到的 x 和 y 坐标分别排序并去重，得到两组唯一的、有序的坐标轴。
        4. 这两组坐标轴构成了一个压缩后的网格。每个原始的力场矩形都可以映射到
           这个压缩网格上的一个小矩形区域。
        5. 创建一个基于压缩坐标尺寸的二维差分数组。
        6. 遍历每个原始力场，将其边界坐标在压缩坐标轴中进行二分查找，
           得到其在压缩网格中的索引。
        7. 在差分数组上对这个压缩后的矩形区域执行 `+1` 的范围增加操作。
        8. 所有力场处理完毕后，对差分数组求二维前缀和，得到每个压缩单元格的力场强度。
        """
        n = len(fields)
        xs, ys = [0] * (n * 2), [0] * (n * 2)
        
        # 收集所有边界坐标 (乘以2以避免处理小数)
        for i, (x, y, side) in enumerate(fields):
            xs[2 * i] = 2 * x - side
            xs[2 * i + 1] = 2 * x + side
            ys[2 * i] = 2 * y - side
            ys[2 * i + 1] = 2 * y + side
            
        # 排序并去重，得到唯一的坐标轴，只有不同的才保留
        xs = sorted(list(set(xs)))
        ys = sorted(list(set(ys)))
        
        size_x = len(xs)
        size_y = len(ys)
        diff = [[0] * (size_y + 2) for _ in range(size_x + 2)]
        
        # 对每个力场，在压缩后的差分矩阵上进行修改
        for x, y, side in fields:
            # 找到力场边界在压缩坐标轴上的索引(rank)
            # bisect_left 实现了二分查找，效率高
            r1 = bisect.bisect_left(xs, 2 * x - side) + 1 # bisect_left返回的是目标值在有序列表中的插入位置。
            c1 = bisect.bisect_left(ys, 2 * y - side) + 1
            # 注意：右边界和上边界在差分矩阵中对应的是块的结束，而不是下一个块的开始
            # rank(v) 找到的是 v 的位置，而这个位置是区间的开始，所以是rank(end)-1
            # 但add操作是[c+1]，所以直接rank(end)即可
            r2 = bisect.bisect_left(xs, 2 * x + side) + 1
            c2 = bisect.bisect_left(ys, 2 * y + side) + 1
            self._add(diff, r1, c1, r2-1, c2-1) #对每个力场调用 add → 在差分数组上标记覆盖

        ans = 0
        # 从差分矩阵进行前缀和还原，并找到最大值
        for i in range(1, size_x + 1):
            for j in range(1, size_y + 1):
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
                ans = max(ans, diff[i][j])
                
        return ans

    def _add(self, diff: List[List[int]], r1: int, c1: int, r2: int, c2: int):
        """二维差分操作"""
        diff[r1][c1] += 1
        diff[r2 + 1][c2 + 1] += 1
        diff[r2 + 1][c1] -= 1
        diff[r1][c2 + 1] -= 1

离散化技巧总结

1. 适用场景：坐标范围大但关键点少
2. 核心步骤：收集→排序→去重→映射
3. 空间优化：从O(坐标范围)降到O(关键点数量)
4. 查找效率：使用二分查找进行坐标映射

算法分析

• 时间复杂度：O(n²log n)
• 空间复杂度：O(n²)
• 优化效果：坐标压缩后空间大大减少

---

技巧总结与应用场景

1. 二维前缀和应用场景

# 适用情况：
# 1. 大量矩形区域查询
# 2. 查询频率远大于修改频率
# 3. 矩阵相对较小，可以承受O(n×m)的预处理

# 核心模板：
def build_prefix_sum(matrix):
    """构建二维前缀和"""
    n, m = len(matrix), len(matrix[0])
    s = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            s[i][j] = matrix[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
    return s

def query_sum(s, r1, c1, r2, c2):
    """查询矩形区域和"""
    return s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1]

2. 二维差分应用场景

# 适用情况：
# 1. 大量矩形区域修改
# 2. 修改完成后批量查询
# 3. 不需要边修改边查询

# 核心模板：
def add_rectangle(diff, r1, c1, r2, c2, val):
    """矩形区域增加val"""
    diff[r1][c1] += val
    diff[r2+1][c1] -= val
    diff[r1][c2+1] -= val
    diff[r2+1][c2+1] += val

def build_result(diff):
    """从差分数组构建结果"""
    n, m = len(diff)-1, len(diff[0])-1
    for i in range(1, n):
        for j in range(1, m):
            diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]

3. 离散化应用场景

# 适用情况：
# 1. 坐标范围很大（如10^9）
# 2. 关键坐标点相对较少
# 3. 需要在坐标上进行区间操作

# 核心模板：
def discretize(coordinates):
    """坐标离散化"""
    # 去重排序
    sorted_coords = sorted(list(set(coordinates)))
    
    # 建立映射
    coord_to_index = {coord: i for i, coord in enumerate(sorted_coords)}
    
    return sorted_coords, coord_to_index

def get_compressed_index(coord, sorted_coords):
    """获取压缩后的索引"""
    return bisect.bisect_left(sorted_coords, coord)

复杂度分析对比

技巧	预处理	单次操作	空间复杂度	适用场景
二维前缀和	O(n×m)	O(1)查询	O(n×m)	多查询少修改
二维差分	O(1)	O(1)修改 + O(n×m)构建	O(n×m)	多修改后查询
离散化	O(k log k)	依赖具体算法	O(k²)	大坐标少关键点

学习建议

1. 理解容斥原理

• 掌握二维前缀和的数学基础
• 理解四个矩形的加减关系
• 练习边界处理技巧

2. 掌握差分思想

• 理解二维差分的四点修改原理
• 熟练掌握差分与前缀和的转换
• 注意边界扩展的重要性

3. 熟练离散化技巧

• 理解坐标压缩的核心思想
• 掌握二分查找在离散化中的应用
• 练习大坐标问题的转换

4. 综合应用能力

• 能够识别适合使用哪种技巧的问题
• 掌握多种技巧的组合使用
• 注意边界条件和特殊情况的处理

5. 调试技巧

• 验证前缀和构建的正确性
• 检查差分操作的边界
• 测试离散化映射的准确性

通过掌握二维前缀和、二维差分和离散化技巧，可以高效解决各种二维矩阵问题。关键在于理解每种技巧的适用场景，以及合理的边界处理和空间优化策略。