Simple Java Solution using Binary Indexed Tree


  • 0
    J
    public class NumArray {
        int [] BIT;
        int r;
        int [] arr;
        public NumArray(int[] nums) {
            if(nums.length ==0) return;
            r = nums.length;
            arr = new int[r];
            BIT = new int[r+1];
            for(int i=0;i<r;i++){
                update(i,nums[i]);
            }
        }
        
        public void update(int i, int val) {
            if(r==0)return;
            int del = val -arr[i];
            arr[i] =val;
            for(int j=i+1;j<=r;j = j + (j&-j)){
                BIT[j] +=del;
            }
        }
        
        public int sumRange(int i, int j) {
            return sum(j+1) - sum(i);
        }
        public int sum(int row){
            int sum =0;
            for(int i = row;i>0; i = i - (i&-i))
            {
                sum = sum+ BIT[i];
            }
            return sum;
        }
    }
    
    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * obj.update(i,val);
     * int param_2 = obj.sumRange(i,j);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.