算法技巧：前缀和数组

package com.algorithm202305.prefix_array;

/**
 * 前缀和数组
 * 一堆数组中的前缀和
 * 区域和检索 - 数组不可变
 * https://leetcode.cn/problems/range-sum-query-immutable/
 */
public class Demo1 {
    class NumArray {
        //前缀数组
        private int[] preSum;

        public NumArray(int[] nums) {
            //记录从1-N的累计和
            preSum = new int[nums.length + 1];
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
        }
        /* 查询闭区间 [left, right] 的累加和 */
        public int sumRange(int left, int right) {
            return preSum[right + 1] - preSum[left];
        }

    }
}

package com.algorithm202305.prefix_array;

/**
 * 二维区域和检索 - 矩阵不可变
 * 二维矩阵前缀和
 * https://leetcode.cn/problems/range-sum-query-2d-immutable/
 */
public class Demo2 {
    class NumMatrix {
        // 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
        private int[][] preSum;

        public NumMatrix(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            if (m == 0 || n == 0) return;
            // 构造前缀和矩阵
            preSum = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    // 计算每个矩阵 [0, 0, i, j] 的元素和
                    //preSum[i][j]：原始矩阵中从 (1,1) 到 (i,j) 的子矩阵内所有元素的总和。
                    //preSum[i-1][j]：原始矩阵中从 (1,1) 到 (i-1,j) 的子矩阵内所有元素的总和。
                    //preSum[i][j-1]：原始矩阵中从 (1,1) 到 (i,j-1) 的子矩阵内所有元素的总和。
                    //preSum[i-1][j-1]：原始矩阵中从 (1,1) 到 (i-1,j-1) 的子矩阵内所有元素的总和。
                    //matrix[i - 1][j - 1]：原始矩阵中当前元素的值。
                    //通过将另外三个项的总和减去 preSum[i-1][j-1]，我们避免了重复计算从 (1,1) 到 (i-1,j-1) 的子矩阵中的元素。
                    preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
                }
            }
        }

        // 计算子矩阵 [x1, y1, x2, y2] 的元素和
        public int sumRegion(int x1, int y1, int x2, int y2) {

            // 目标矩阵之和由四个相邻矩阵运算获得
            return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
        }
    }
}