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:

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

Segment tree.

class SegTreeNode{
public:
    SegTreeNode * left, * right;
    int sum;
    int leftidx, rightidx;
    SegTreeNode():sum(0), leftidx(0), rightidx(0), left(nullptr), right(nullptr){}
};

class NumArray {
public:
    SegTreeNode * root;
    NumArray(vector<int> &nums) {
        if(nums.size() == 0) return ;
        root = buildSegmentTree(nums, 0, nums.size() - 1);    
    }
    SegTreeNode* buildSegmentTree(vector<int>& nums, int start, int end){
        SegTreeNode * node = new SegTreeNode();
        node->leftidx = start;
        node->rightidx = end;
        int mid = (start + end) / 2;
        if(start == end){
            node->sum = nums[start];
        }else{
            node->left = buildSegmentTree(nums, start, mid);
            node->right = buildSegmentTree(nums, mid + 1, end);
            node->sum = node->left->sum + node->right->sum;
        }
        return node;
    }
    void update(int i, int val) {
        _update(root, i, val);
    }
    void _update(SegTreeNode* node, int i, int val){
        if(node->leftidx == node->rightidx && node->leftidx == i){
            node->sum = val;
        }else{
            int mid = (node->leftidx + node->rightidx) / 2;
            if(i <= mid){
                _update(node->left, i, val);
            }else{
                _update(node->right, i, val);
            }
            node->sum = node->left->sum + node->right->sum;
        }
    }

    int sumRange(int i, int j) {
        return _sumRange(root, i, j);
    }
    int _sumRange(SegTreeNode* node, int i, int j){
        if(node->leftidx > j || node->rightidx < i){
            return 0;
        }
        else if(node->leftidx >= i && node->rightidx <= j){
            return node->sum;
        }else{
            return _sumRange(node->left, i, j) + _sumRange(node->right, i, j);
        }
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);