Question

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Code

class TreeNode {
    public int start;
    public int end;
    public int sum;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int start, int end, int sum) {
        this.start = start;
        this.end = end;
        this.sum = sum;
    }
    
    public TreeNode(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
 
public class NumArray {
    TreeNode root = null;
 
    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) return;
        
        root = buildTree(nums, 0, nums.length - 1);
    }
 
    void update(int i, int val) {
        updateHelper(root, i, val);
    }
 
    void updateHelper(TreeNode root, int i, int val) {
        if (root == null) return;
        
        if (root.start == i && root.end == i) {
            root.sum = val;
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        if (i <= mid) {
            updateHelper(root.left, i, val);
        } else {
            updateHelper(root.right, i, val);
        }
        
        root.sum = root.left.sum + root.right.sum;
    }
 
    public int sumRange(int i, int j) {
        return sumRangeHelper(root, i, j);
    }
 
    public int sumRangeHelper(TreeNode root, int i, int j) {
        if (root == null || i > j || root.start > i || root.end < j) return 0;
        
        if (i == root.start && j == root.end) return root.sum;
        
        int mid = root.start + (root.end - root.start) / 2;
        int result = sumRangeHelper(root.left, i, Math.min(mid, j)) + sumRangeHelper(root.right, Math.max(i, mid + 1), j);
        
        return result;
    }
 
    public TreeNode buildTree(int[] nums, int i, int j) {
        if (nums == null || nums.length == 0 || i > j) return null;
        if (i == j) {
            TreeNode node = new TreeNode(i, j, nums[i]);
            return node;
        }
        
        TreeNode curr = new TreeNode(i, j);
        int mid = i + (j - i) / 2;
        curr.left = buildTree(nums, i, mid);
        curr.right = buildTree(nums, mid + 1, j);
        
        curr.sum = curr.left.sum + curr.right.sum;
        
        return curr;
    }
}

Solution

使用segment tree实现。

start和end分别表示range的上下界。
sum表示该range的和。
left和right分别为左右孩子节点，range范围各取一半。
所有的叶子节点start = end，sum = 该数的值。

更新时，需先找到待更新的叶子节点，将此节点的sum值更新后，再更新所有与此相关的节点的sum值。

求range的和时，通过递归求得两部分的和后相加。