307. Range Sum Query - Mutable

 1 class NumArray {
 2     int[] preSum;
 3     int[] arr;
 4     public NumArray(int[] nums) {
 5         arr = nums;
 6         preSum = new int[nums.length+1];
 7         preSum[0] = 0;
 8         for(int i = 0; i < nums.length; i++){
 9             preSum[i+1] = preSum[i] + nums[i];
10         }
11         
12     }
13     
14     public void update(int i, int val) {
15         for(int j = i+1; j < preSum.length; j++){
16             preSum[j] = preSum[j] - (arr[i]) + val;
17         }
18         arr[i] = val;
19         
20     }
21     
22     public int sumRange(int i, int j) {
23         return preSum[j+1] - preSum[i];
24         
25     }
26 }