class NumArray { int[] sums; int[] nums; int n; public NumArray(int[] nums) { n = nums.length; sums = new int[n+1]; this.nums = nums; for(int i = 0; i < n; i++){ add(i,nums); } } private void add(int index, int item){ int i = index+1; while(i<=n){ sums+=item; i += last(i); } } private int get(int index){ int i = index+1; int ans = 0; while(i>0){ ans += sums; i -= last(i); } return ans; } private int last(int a){ return a & (-a); } public void update(int index, int val) { int add = val-nums[index]; nums[index] = val; add(index,add); } public int sumRange(int left, int right) { return get(right)-get(left-1); }}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.update(index,val); * int param_2 = obj.sumRange(left,right); */
