Range Sum Query

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

• Time: O(n)
• Space: O(n)

public class NumArray {
    int[] dp;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i - 1] + nums[i];
        }
    }

    public int sumRange(int j, int i) {
        return j > 0 ? dp[i] - dp[j - 1] : dp[i];
    }
}

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the dp of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

• Time: O(n)
• Space: O(n)

public class NumMatrix {
    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 
                         - dp[i - 1][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1]
             - dp[row2 + 1][col1] + dp[row1 + 1][col1 + 1];
    }
}