前缀和
1. 一维前缀和
前缀和是一种重要的数据结构技巧，它可以帮助我们快速计算一个数组的任意区间内所有元素的和。前缀和数组是一个辅助数组，其中每个元素表示原数组中从第一个元素到当前位置元素的和。 例如，给定一个数组 arr，其前缀和数组 prefixSum 可以这样计算：
prefixSum[i] = arr[0] + arr[1] + ... + arr[i]
这样，如果我们想计算 arr 中从索引 l 到索引 r 的元素和，我们只需要计算 prefixSum[r] - prefixSum[l-1]（如果 l 为0，则直接返回 prefixSum[r]）。 下面是一个简单的Java代码示例，展示了如何构建前缀和数组并使用它来计算区间和：
public class PrefixSum {
public static int[] buildPrefixSum(int[] arr) {
int n = arr.length;
int[] prefixSum = new int[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
return prefixSum;
}
public static int rangeSum(int[] prefixSum, int l, int r) {
if (l == 0) {
return prefixSum[r];
} else {
return prefixSum[r] - prefixSum[l - 1];
}
}
public static void main(String[] args) {
int[] arr = {3, 5, 2, 8, 6};
int[] prefixSum = buildPrefixSum(arr);
System.out.println("Prefix Sum: " + Arrays.toString(prefixSum));
int l = 1;
int r = 3;
System.out.println("Sum of range [" + l + ", " + r + "]: " + rangeSum(prefixSum, l, r));
}
}
在这个例子中，buildPrefixSum 函数用于构建前缀和数组，而 rangeSum 函数用于计算指定区间的和。在 main 函数中，我们创建了一个示例数组，构建了它的前缀和数组，并计算了索引1到3的区间和。
前缀和数组长度加1，方便处理边界情况
public class PrefixSum {
public static int[] prefixSum(int[] arr) {
int n = arr.length;
int[] prefix = new int[n + 1];
prefix[0] = 0; // 初始前缀和为0
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + arr[i - 1];
}
return prefix;
}
public static int rangeSum(int[] prefix, int left, int right) {
// 计算区间和
return prefix[right + 1] - prefix[left];
}
public static void main(String[] args) {
int[] arr = { 3, 5, 2, 8, 6 };
int[] prefix = prefixSum(arr);
System.out.println("原数组：" + Arrays.toString(arr));
System.out.println("前缀和数组：" + Arrays.toString(prefix));
System.out.println("区间和[1, 3]：" + rangeSum(prefix, 1, 3)); // 输出区间和[1, 3]
}
}
2. 二维前缀和
二维前缀和是一种用于快速计算二维数组中任意子矩阵元素和的数据结构。与一维前缀和类似，二维前缀和也是通过预处理来构建一个辅助矩阵，使得我们可以快速查询任意子矩阵的和。 给定一个二维数组 arr，其前缀和矩阵 prefixSum 可以这样计算：
prefixSum[i][j] = arr[0][0] + arr[0][1] + ... + arr[i][j]
这样，如果我们想计算 arr 中以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵的和，我们可以使用以下公式：
sum = prefixSum[x2][y2] - prefixSum[x1-1][y2] - prefixSum[x2][y1-1] + prefixSum[x1-1][y1-1]
这里，prefixSum[x2][y2] 表示从 (0, 0) 到 (x2, y2) 的所有元素的和，prefixSum[x1-1][y2] 表示从 (0, 0) 到 (x1-1, y2) 的所有元素的和，以此类推。通过这种方式，我们可以避免重复计算子矩阵中的元素。 下面是一个简单的Java代码示例，展示了如何构建二维前缀和矩阵并使用它来计算子矩阵的和：
import java.util.Arrays;
public class PrefixSum2D {
public static int[][] buildPrefixSum2D(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
int[][] prefixSum = new int[rows + 1][cols + 1];
// 计算偏移前缀和
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
prefixSum[i][j] = arr[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
}
}
return prefixSum;
}
public static int rangeSum2D(int[][] prefixSum, int x1, int y1, int x2, int y2) {
// 由于偏移，查询的坐标需要加1
return prefixSum[x2 + 1][y2 + 1] - prefixSum[x1][y2 + 1] - prefixSum[x2 + 1][y1] + prefixSum[x1][y1];
}
public static void main(String[] args) {
int[][] arr = {
{3, 5, 2, 8},
{1, 7, 6, 2},
{4, 3, 2, 5}
};
int[][] prefixSum = buildOffsetPrefixSum2D(arr);
System.out.println("2D Prefix Sum:");
for (int[] row : prefixSum) {
System.out.println(Arrays.toString(row));
}
int x1 = 0; // 左上角坐标
int y1 = 0;
int x2 = 1; // 右下角坐标
int y2 = 2;
System.out.println("Sum of range [" + x1 + ", " + y1 + "] to [" + x2 + ", " + y2 + "]: " + rangeSum2D(prefixSum, x1, y1, x2, y2));
}
}
在这个例子中，buildPrefixSum2D 函数用于构建偏移的二维前缀和矩阵，而 rangeSum2D 函数用于计算指定子矩阵的和。在 main 函数中，我们创建了一个示例二维数组，构建了它的偏移二维前缀和矩阵，并计算了以 (0, 0) 为左上角，(1, 2) 为右下角的子矩阵的和。