307. 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:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(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.

Solution:

Segment tree.

Leetcode solution section has very detailed explanation of segment tree. Please refer there.

Basically segment tree is a binary tree storing information of a segment. In this case it storing the summation of the segment. 

 class NumArray {  
   int[] rangeTree;  
   int n;  
   public NumArray(int[] nums) {  
     if(nums==null || nums.length==0) return;  
     n=nums.length;  
     rangeTree=new int[n*2-1];  
     for(int i=0;i<rangeTree.length;i++){  
       if(i<n) rangeTree[i]=nums[i];  
       else{  
         rangeTree[i]=rangeTree[(i-n)*2]+rangeTree[(i-n)*2+1];  
       }  
     }      
   }  
   public void update(int i, int val) {  
     int diff=val-rangeTree[i];  
     while(i<rangeTree.length){  
       rangeTree[i]+=diff;  
       i=i/2+n;  
     }      
   }  
   public int sumRange(int i, int j) {  
     if(i==j) return rangeTree[i];  
     if(i>j) return 0;  
     if(i%2==1) return sumRange(i+1,j)+rangeTree[i];  
     if(j%2==0) return sumRange(i,j-1)+rangeTree[j];  
     return sumRange(i/2+n,j/2+n);  
   }  
 }