Range Query, Immutable and Mutable

Range Sum Query - Immutable

Immutable求sum，要想到prifixSum。

public class NumArray {

    int[] prefixSum;

    public NumArray(int[] nums) {
        int n = nums.length;
        prefixSum = new int[n + 1];

        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += nums[i - 1];
            prefixSum[i] = sum;
        }
    }

    public int sumRange(int i, int j) {
        return prefixSum[j + 1] - prefixSum[i];
    }
}

Range Sum Query 2D - Immutable

public class NumMatrix {

    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return;
        }

        int m = matrix.length, n = matrix[0].length;
        dp = new int[m + 1][n + 1];

        int sum = 0;
        for (int i = 1; i <= m; i++) {
            sum += matrix[i - 1][0];
            dp[i][1] = sum;
        }

        sum = 0;
        for (int j = 1; j <= n; j++) {
            sum += matrix[0][j - 1];
            dp[1][j] = sum;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (dp == null) {
            return 0;
        }

        int smallRow = Math.min(row1, row2);
        int bigRow = Math.max(row1, row2);
        int smallCol = Math.min(col1, col2);
        int bigCol = Math.max(col1, col2);

        return dp[bigRow + 1][bigCol + 1] - dp[bigRow + 1][smallCol] - dp[smallRow][bigCol + 1] + dp[smallRow][smallCol];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Range Sum Query - Mutable

Mutable且一维时，segment tree是个选择。

public class NumArray {

    SegmentTreeNode root;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        root = build(nums, 0, nums.length - 1);
    }

    public void update(int i, int val) {
        modify(root, i, val);
    }

    public int sumRange(int i, int j) {
        return query(root, i, j);
    }

    private int query(SegmentTreeNode root, int start, int end) {
        if (start <= root.start && end >= root.end) {
            return root.sum;
        } 

        int mid = root.start + (root.end - root.start) / 2;
        if (mid >= end) {
            return query(root.left, start, end);
        } else if (mid + 1 <= start) {
            return query(root.right, start, end);
        }

        int left = query(root.left, start, mid);
        int right = query(root.right, mid + 1, end);
        return left + right;
    }

    private SegmentTreeNode modify(SegmentTreeNode root, int i, int val) {
        if (root == null || i < root.start || i > root.end) {
            return root;
        } else if (root.start == i && root.end == i) {
            root.sum = val;
            return root;
        }

        SegmentTreeNode left = modify(root.left, i, val);
        SegmentTreeNode right = modify(root.right, i, val);
        root.sum = left.sum + right.sum;
        return root;
    }

    private SegmentTreeNode build(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        SegmentTreeNode root = new SegmentTreeNode(start, end, nums[start]);
        if (start < end) {
            int mid = start + (end - start) / 2;
            root.left = build(nums, start, mid);
            root.right = build(nums, mid + 1, end);
            root.sum = root.left.sum + root.right.sum;
        }
        return root;
    }
}

class SegmentTreeNode {
    int start, end, sum;
    SegmentTreeNode left, right;

    public SegmentTreeNode(int start, int end, int sum) {
        this.start = start;
        this.end = end;
        this.sum = sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */