https://leetcode.com/problems/range-sum-query-mutable/

range-sum-query-mutable-v1.java

class NumArray {
    class SegmentTreeNode {
        SegmentTreeNode left;
        SegmentTreeNode right;
        int sum;
        int start;
        int end;
        
        public SegmentTreeNode(int start, int end){
            this.left = null;
            this.right = null;
            this.sum = 0;
            this.start = start;
            this.end = end;
        }
    }
    
    
    public SegmentTreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        SegmentTreeNode node = new SegmentTreeNode(start, end);
        if (start == end) {
            node.sum += nums[start];
        } else {
            
            int mid = start + (end - start) / 2;
            node.left = buildTree(nums, start, mid);
            node.right = buildTree(nums, mid + 1, end);
            if (node.left != null) { // no need to do null check
                node.sum += node.left.sum;
            }
            if (node.right != null) {
                node.sum += node.right.sum;
            }
        }
        return node;
    }
    
    
    SegmentTreeNode root;
    
    public NumArray(int[] nums) {
        this.root = buildTree(nums, 0, nums.length - 1);
        
    }
    
    public void updateTree(SegmentTreeNode node, int i, int val) {
        if (node == null) { // no need to check
            return;
        }
        if (node.start == i && node.end == i) {
            node.sum = val;
            return; 
        }
        int mid = node.start + (node.end - node.start) / 2;
        if (i <= mid) {
            updateTree(node.left, i, val);
        } else {
            updateTree(node.right, i, val);
        }
        // update sum
        node.sum = node.left.sum + node.right.sum;
    }
    
    
    public void update(int i, int val) {
        updateTree(this.root, i, val);
    }
    
    public int sumRangeHelper(SegmentTreeNode node, int i, int j) {
        if (node.start == i && node.end == j) {
            return node.sum;
        }
        int mid = node.start + (node.end - node.start) / 2;
        if (i > mid) {
            return sumRangeHelper(node.right, i, j);
        }
        if (j <= mid) {
            return sumRangeHelper(node.left, i, j);
        }
        return sumRangeHelper(node.left, i, mid) + sumRangeHelper(node.right, mid + 1, j); 
    }    
    
    public int sumRange(int i, int j) {
        return sumRangeHelper(this.root, i, j);
    }
}

/**
 * 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);
 */

range-sum-query-mutable-v2.java

class NumArray {
    class BinaryIndexedTree {
        int[] arr;
        int[] nums;
        
        public BinaryIndexedTree(int n, int[] nums) {
            this.arr = new int[n + 1];
            this.nums = nums;
        }
        
        private int lowbit(int x) {
            return x & (-x);
        }
        
        public void update(int i, int val) {
            i += 1; // index i -> ith number
            while(i < arr.length) {
                arr[i] += val;
                i += lowbit(i);
            }
        }
        
        public int query(int i) {
            int sum = 0;
            i += 1; // index i -> ith number
            while(i > 0) {
                sum += arr[i];
                i -= lowbit(i);
            }
            return sum;
        }
    }
    
    
    BinaryIndexedTree btree;
    public NumArray(int[] nums) {
        this.btree = new BinaryIndexedTree(nums.length, nums);
        for (int i = 0; i < nums.length; i++) {
            this.btree.update(i, nums[i]);
        }
    }
    
    public void update(int i, int val) {
        int diff = val - this.btree.nums[i];
        this.btree.nums[i] = val;
        this.btree.update(i, diff);
    }
    
    public int sumRange(int i, int j) {
        return this.btree.query(j) - this.btree.query(i-1);
    }
}

/**
 * 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);
 */