307. Range Sum Query - Mutable

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

求解范围内max/min/sum/count且范围内的元素值会不断改变（但总size不变），线段树和二叉索引树是常用方法。除了常规真的定义一颗二叉树，每个结点有范围和感兴趣的值外，还可以用完全二叉树的表示方法即一个数组。线段树叶子结点表示范围大小为1的点，即原nums数组元素，放在N-1~2 N - 1。倒着遍历，叶结点两两合并的父节点存更大范围的和，nodes[i] = nodes[i * 2] + nodes[i * 2 + 1]。这样建好树后每次更新时也是倒着先从叶结点层层往上更新值。求sumRange也是从叶子开始，用两个指针分别指向最外面的两个元素，如果i指向的是右子结点说明它代表的区间已经是边界，不能把它父结点的算进来，因此把它的值加上并把范围缩小1个。j同理。当i > j时遍历结束。解法参考了这里。

/*
 * @lc app=leetcode id=307 lang=cpp
 *
 * [307] Range Sum Query - Mutable
 *
 * https://leetcode.com/problems/range-sum-query-mutable/description/
 *
 * algorithms
 * Medium (29.96%)
 * Likes:    804
 * Dislikes: 66
 * Total Accepted:    79.7K
 * Total Submissions: 264.7K
 * Testcase Example:  '["NumArray","sumRange","update","sumRange"]\n[[[1,3,5]],[0,2],[1,2],[0,2]]'
 *
 * 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.
 * 
 * 
 */
class NumArray {
private:
    vector<int> nodes;
    int N;
public:
    NumArray(vector<int>& nums) {
       N = nums.size();
       nodes.resize(2 * N);
       // nums作为叶子
       for (int i = N; i < 2 * N; ++i) {
           nodes[i] = nums[i - N];
       }
       for (int i = N - 1; i >= 0; --i) {
           nodes[i] = nodes[i * 2] + nodes[i * 2 + 1];
       }
    }
    
    void update(int i, int val) {
        nodes[i += N] = val;
        while (i > 0) {
            nodes[i / 2] = nodes[i] + nodes[i ^ 1];
            i /= 2;
        }
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        for (i += N, j += N; i <= j; i /= 2, j /= 2) {
            // 左边界为右结点, 加上自己，并把范围缩小1。
            if ((i & 1) == 1) sum += nodes[i++];
            // 右边界为左结点, 加上自己，并把范围缩小1。
            if ((j & 1) == 0) sum += nodes[j--];
        }
        return 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);
 */