「算法」前缀和

前���和主要解决求数组中某段区间元素和的问题，使用前缀和解决问题的步骤如下:

1. 预处理一个前缀和数组
2. 使用这个数组

一维前缀和

现在有一个一维数组nums

• 预处理前缀和数组

  定义一个数组 dp[]，dp[i]表示 nums 中 [0,i-1] 区间的元素和，那我们就有 dp[i] == dp[i-1] + nums[i-1]这个递推关系

  然后就可以来初始化 dp 数组：

  for(int i = 1;i     int[] dp;    public NumArray(int[] nums) {        int len = nums.length;        dp = new int[len+1];        for(int i = 1;i         return dp[right+1]-dp[left];    }}        int m = matrix.length;        int n = matrix[0].length;        arr = new int[m+1][n+1];        for(int i = 1;i             for(int j = 1;j                 arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] + matrix[i-1][j-1];            }        }}        x1++; y1++; x2++; y2++;        return arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1];    }    int[][] arr;    public NumMatrix(int[][] matrix) {        int m = matrix.length;        int n = matrix[0].length;        arr = new int[m+1][n+1];        for(int i = 1;i             for(int j = 1;j                 arr[i][j] = arr[i][j-1] + arr[i-1][j]+ matrix[i-1][j-1] - arr[i-1][j-1];            }        }    }        public int sumRegion(int x1, int y1, int x2, int y2) {        x1++; y1++; x2++; y2++;        return arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1];    }}