原题链接在这里：

题目：

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) -> 9update(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.

题解：

与相似。更新与求和都很多，利用Binary Indexed Tree.

参考帖子

更新时，更新binary indexed tree的每层parent node. 求和时, 取该点往下所有根节点的和. 更新与求和都能维持O(log n)时间.

Time Complexity: NumArray, O(nlogn). update, O(logn). sumRange, O(logn). n = nums.length.

Space: O(n).

AC Java:

1 public class NumArray { 2     int [] bit; 3     int [] nums; 4      5     public NumArray(int[] nums) { 6         if(nums == null || nums.length == 0){ 7             return; 8         } 9         this.bit = new int[nums.length+1];10         this.nums = new int[nums.length];11         for(int i = 0; i
     
       0){31             sum += this.bit[i];32             i -= (i&-i);33         }34         return sum;35     }36 }37 38 /**39  * Your NumArray object will be instantiated and called as such:40  * NumArray obj = new NumArray(nums);41  * obj.update(i,val);42  * int param_2 = obj.sumRange(i,j);43  */
     

 跟上.