二维差分 acwing

二维差分是一种常用的数据结构和算法巧，用于高效地处理二维矩阵区间的更新和查询操作。它可以在O(1)的时间复杂度内完成区间的更新和查询操作，相比传统的暴力遍历方法，具有更高的效率。

二维差分的基本思想是将原始矩阵转化为一个差分矩阵，差分矩阵中的每个元素表示原始矩阵中相邻元素之间的差值。通过对差分矩阵进行预处理，可以实现对原始矩阵区间的更新和查询操作。

具体来说，二维差分的操作包括两个步骤：预处理和操作。预处理阶段，需要根据原始矩阵构建差分矩阵；操作阶段，可以通过对差分矩阵的更新来实现对原始矩阵区间的更新，同时可以通过对差分矩阵的求和来实现对原始矩阵区间的查询。

下面是二维差分的基本操作：
1. 构建差分矩阵：对于原始矩阵A，构建一个差分矩阵B，其中B[i][j] = A[i][j] - A[i-1][j] - A[i][j-1] + A[i-1][j-1]。
2. 区间更新：对于原始矩阵A的一个区间[left, right] x [top, bottom]，将差分矩阵B的相应位置进行更新，即B[left][top] += val，B[right+1][top] -= val，B[left][bottom+1] -= val，B[right+1][bottom+1] += val。
3. 区间查询：对于原始矩阵A的一个区间[left, right] x [top, bottom]，通过求和差分矩阵B的相应位置得到区间和，即sum = B[right][bottom] - B[left-1][bottom] - B[right][top-1] + B[left-1][top-1]。

二维差分可以广泛应用于各种算法问题，例如矩阵区间求和、矩阵区间更新等。它的时间复杂度较低，适用于处理大规模的数据。