二维前缀和与差分详解：原理、实现及应用

二维前缀和与差分详解：原理、实现及应用

引用

CSDN

1.

https://blog.csdn.net/2301_77160836/article/details/136824769

二维前缀和与二维差分是算法竞赛中常见的数据结构和算法技巧，主要用于解决矩阵元素的区间加减问题。本文将详细介绍二维前缀和与差分的概念、原理及应用，并通过具体的例子和代码实现帮助读者深入理解。

二维前缀和

二维前缀和的计算方法与一维前缀和类似，但需要考虑二维数组的特性。给定一个二维数组a，其前缀和数组b可以通过以下递推公式计算：

为了方便计算，通常在定义数组a和b时会多定义一行和一列的0，这样可以避免边界条件的特殊处理。

二维差分

差分可以看作是前缀和的逆运算。给定一个二维数组a，其差分数组b可以通过以下公式计算：

方法一：直观理解

这种方法通过构造差分矩阵来实现区间加减操作。具体步骤如下：

1. 初始化差分矩阵b，大小为(n+2) x (m+2)，其中n和m分别是原矩阵的行数和列数。
2. 对于每个区间加减操作(x1, y1, x2, y2, c)，在差分矩阵b中进行以下更新：

• b[x1][y1] += c
• b[x1][y2+1] -= c
• b[x2+1][y1] -= c
• b[x2+1][y2+1] += c

这种方法的时间复杂度为O(1)，可以显著优化区间加减操作的效率。

方法二：优化实现

这种方法通过"曲线救国"的方式构造差分矩阵。具体步骤如下：

1. 初始化差分矩阵b，大小为(n+2) x (m+2)。
2. 对于原矩阵a中的每个元素a[i][j]，在差分矩阵b中执行以下操作：

• b[i][j] += a[i][j]
• b[i][j+1] -= a[i][j]
• b[i+1][j] -= a[i][j]
• b[i+1][j+1] += a[i][j]

这种方法在构造差分矩阵时需要O(n*m)的时间复杂度，但在后续的区间加减操作中仍然保持O(1)的时间复杂度。

代码实现

以下是使用Python实现的二维差分算法：

def update_diff_matrix(b, x1, y1, x2, y2, c):
    b[x1][y1] += c
    b[x1][y2 + 1] -= c
    b[x2 + 1][y1] -= c
    b[x2 + 1][y2 + 1] += c

def construct_diff_matrix(a):
    n, m = len(a), len(a[0])
    b = [[0] * (m + 2) for _ in range(n + 2)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            b[i][j] = a[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1] + a[i][j]
    return b

def apply_operations(a, operations):
    n, m = len(a), len(a[0])
    b = construct_diff_matrix(a)
    for x1, y1, x2, y2, c in operations:
        update_diff_matrix(b, x1, y1, x2, y2, c)
    return b

def reconstruct_matrix(b):
    n, m = len(b) - 2, len(b[0]) - 2
    res = [[0] * m for _ in range(n)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            res[i - 1][j - 1] = b[i][j] - b[i - 1][j] - b[i][j - 1] + b[i - 1][j - 1]
    return res

# Example usage
a = [
    [1, 2, 2, 1],
    [3, 2, 2, 1],
    [1, 1, 1, 1]
]
operations = [
    (1, 1, 2, 2, 1),
    (1, 3, 2, 3, 2),
    (3, 1, 3, 4, 1)
]

b = apply_operations(a, operations)
result = reconstruct_matrix(b)
for row in result:
    print(row)

总结

二维前缀和与差分是算法竞赛中常见的数据结构和算法技巧，主要用于解决矩阵元素的区间加减问题。通过构造差分矩阵，可以将区间加减操作的时间复杂度从O(n*m)优化到O(1)，显著提高算法效率。本文详细介绍了二维前缀和与差分的概念、原理及应用，并通过具体的例子和代码实现帮助读者深入理解。