Range Sum Query - Mutable: https://leetcode.com/problems/range-sum-query-mutable/#/description

• 如何 build tree 取决于 query by index or query by value
• For a given interval, update and query sum.

public class NumArray {

    private class SegmentTreeNode {

        int start;
        int end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode right;

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

    SegmentTreeNode root;

    public NumArray(int[] nums) {
        this.root = build(nums, 0, nums.length - 1);        
    }

    private SegmentTreeNode build(int[] nums, int start, int end) {

        if (start > end || nums == null || nums.length == 0) return null;
        if (start == end) return new SegmentTreeNode(start, end, nums[start]);

        int mid = start + (end - start) / 2;

        SegmentTreeNode left = build(nums, start, mid);
        SegmentTreeNode right = build(nums, mid + 1, end);

        int sum = left.sum + right.sum;

        SegmentTreeNode node = new SegmentTreeNode(start, end, sum);

        node.left = left;
        node.right = right;

        return node;                
    }

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

    private void update(SegmentTreeNode node, int i, int val) {

        if (node == null) return;
        if (i > node.end || i < node.start) return;
        if (i == node.start && i == node.end) {
            node.sum = val;
            return;
        }

        update(node.left, i, val);
        update(node.right, i, val);

        node.sum = node.left.sum + node.right.sum;
        return;
    }

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

    private int sumRange(SegmentTreeNode node, int i, int j) {

        if (node == null) return 0;
        if (i > node.end || j < node.start) return 0;

        i = Math.max(i, node.start);
        j = Math.min(j, node.end);

        if (i == node.start && j == node.end) {
            return node.sum;
        }

        int left = sumRange(node.left, i, j);
        int right = sumRange(node.right, i, j);

        return left + right;        
    }
}

Range Sum Query - Immutable: https://leetcode.com/problems/range-sum-query-immutable/#/description

• cf previous one: this one only cares Query, so Segment Tree will be overkilled.
• Best case to apply Segment Tree:
  • Frequent update &&
  • Frequent query
• DP prefix sum

    int[] prefixSum;
    public NumArray(int[] nums) {

        if (nums == null || nums.length == 0) {
            return;
        }

        prefixSum = new int[nums.length + 1];
        prefixSum[0] = 0;        

        for (int i = 0; i < nums.length; i++) {            
            prefixSum[i + 1] = nums[i] + prefixSum[i];
        }
    }

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

Range Sum Query 2D - Immutable:

• DP

int[][] dp;

public NumMatrix(int[][] matrix) {
    if(matrix == null || matrix.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 - 1][j - 1];
        }
    }
}

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][col1];
}

Fenwick Tree (Binary Index Tree)

• build O(nlogn)
• update O(logn)
• query O(logn)
• Fenwick Tree 主要用于求各种维度的区间 sum，主要缺点在于建树时间长于 segment tree ，需要 O(n log n) 时间 > Segment Tree O(n). 主要优点是好写，而且非常容易扩展到多维情况。space is O(n), better than segment tree
• https://mnmunknown.gitbooks.io/algorithm-notes/content/66,_tree,_fenwick_tree_binary_indexed_tree.html

• sum: getParent() index -= (index & -index)

• update: getNext() index += (index & -index)

• there is a dummy node. so total length is nums.length + 1

range sum query - mutable

public class NumArray {
    int[] fenwickTree;
    int length;
    int[] arr;
    public NumArray(int[] nums) {
        length = nums.length;
        arr = new int[length];
        fenwickTree = new int[length + 1];

        for(int i = 0; i < length; i++){
            update(i, nums[i]);
        }
    }

    void update(int i, int val) {
        int diff = val - arr[i];
        arr[i] = val;
        // propogate to next 
        for(int index = i + 1; index <= length; index += (index & -index)){
            fenwickTree[index] += diff;
        }
    }

    private int getSum(int i){
        int sum = 0;
        while(i > 0){
            sum += fenwickTree[i];
            i -= (i & -i);
        }
        return sum;
    }

    public int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }
}

range sum query 2D - mutable

public class NumMatrix {
    int[][] fenwickTree;
    int[][] nums;
    int rows;
    int cols;

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

        rows = matrix.length;
        cols = matrix[0].length;
        fenwickTree = new int[rows + 1][cols + 1];
        nums = new int[rows][cols];

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        int diff = val - nums[row][col];
        nums[row][col] = val;
        for(int i = row + 1; i <= rows; i += (i & -i)){
            for(int j = col + 1; j <= cols; j += (j & -j)){
                fenwickTree[i][j] += diff;
            }
        }
    }

    private int getSum(int row, int col){
        int sum = 0;
        for(int i = row; i > 0; i -= (i & -i)){
            for(int j = col; j > 0; j -= (j & -j)){
                sum += fenwickTree[i][j];
            }
        }
        return sum;
    }

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

submatrix sum