Range Sum Query - Mutable

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:
1. Given nums = [1, 3, 5]
2. 3. sumRange(0, 2) -> 9
4. update(1, 2)
5. 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.

Solution:
1. public class NumArray {
2. int[] arr; // stores nums[]
3. int[] BITree; // binary indexed tree
4. 5. public NumArray(int[] nums) {
6. int n = nums.length;
7. arr = new int[n];
8. BITree = new int[n + 1];
9. 10. for (int i = 0; i < n; i++) {
11. update(i, nums[i]); // init BITree[]
12. arr[i] = nums[i]; // init arr[]
13. }
14. }
15. 16. void update(int i, int val) {
17. int diff = val - arr[i]; // get the diff
18. arr[i] = val; // update arr[]
19. 20. i++;
21. while (i <= arr.length) {
22. BITree[i] += diff; // update BITree[]
23. i += i & (-i); // update index to that of parent
24. }
25. }
26. 27. int getSum(int i) {
28. int sum = 0;
29. 30. i++;
31. while (i > 0) {
32. sum += BITree[i]; // accumulate the sum
33. i -= i & (-i); // move index to parent node
34. }
35. return sum;
36. }
37. 38. public int sumRange(int i, int j) {
39. return getSum(j) - getSum(i - 1);
40. }
41. }
42. 43. // Your NumArray object will be instantiated and called as such:
44. // NumArray numArray = new NumArray(nums);
45. // numArray.sumRange(0, 1);
46. // numArray.update(1, 10);
47. // numArray.sumRange(1, 2);