My 14 ms Accepted Java Solution


  • 0

    '''
    public class NumArray {

    int[] sums;
    int[] leaf;
    int n;
    
    
    
    private void getSize(int l)
    {
        int s=1;
        while(s<=l)
        {
            s<<=1;
        }
        n= s<<1;
     
    }
    
    public NumArray(int[] nums) {
        if(nums!=null && nums.length!=0)
        {
        
        getSize(nums.length);
        sums=new int[n];
        leaf=new int[nums.length];
        fillSums(0,nums.length-1,0,nums);
        }
        
    }
    
    private void fillSums(int s, int e, int idx,int[] arr)
    {
        if(s==e)
        {
            sums[idx]=arr[s];
            leaf[s]=idx;
            return;
        }
        
        int mid=(s+e)/2;
        fillSums(s,mid,2*idx+1,arr);
        fillSums(mid+1,e,2*idx+2,arr);
        sums[idx]=sums[2*idx+1]+sums[2*idx+2];
    }
    
    void update(int i, int val) {
        if(i>=0 && i<leaf.length)
        {
            int diff=val-sums[leaf[i]];
            sums[leaf[i]]=val;
            int idx=leaf[i];
            
            while(idx!=0)
            {
                int p=idx%2==0?idx/2-1:idx/2;
                sums[p]+=diff;
                idx=p;
            }
        }
        
    }
    
    private int sumHelper(int start,int end, int is,int ie, int idx)
    {
     
        
        if(is>end||ie<start)
        {
            return 0;
        }
        if(start<=is && end>=ie)
        {
            return sums[idx];
        }
        int mid=(is+ie)/2;
        int left=sumHelper(start,end,is,mid,2*idx+1);
        int right=sumHelper(start,end,mid+1,ie,2*idx+2);
        return left+right;
    }
    
    public int sumRange(int i, int j) {
        if((i>=0 && j<leaf.length) && i<=j)
        {
        return sumHelper(i,j,0,leaf.length-1,0);
        }
        return 0;
        
    }
    

    }
    '''


Log in to reply
 

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