Solutions using Binary Indexed tree and Segment tree


  • 0

    Binary indexed tree version

    public class NumArray {
        int[] bit;
        public NumArray(int[] nums) {
            bit = new int[nums.length+1];
            for(int i=0;i<nums.length;i++)
            {
                int index=i+1;
                while(index<=nums.length)
                {
                    bit[index]+=nums[i];
                    index+=index&(-index);
                }
            }
        }
        
        public int sumRange(int i, int j) {
            return getSum(j)-getSum(i-1);
        }
        
        public int getSum(int i)
        {
            int index=i+1;
            int sum=0;
            while(index>0)
            {
                sum+=bit[index];
                index-=index&(-index);
            }
            return sum;
        }
    }
    

    segment tree version

    
    public class NumArray {
        int [] st;
        int len ;
        public NumArray(int[] nums) {
            
            // tree height log_2 n
            len=nums.length;
             if(len<=0) return;
            int h = (int)Math.ceil(Math.log(len)/Math.log(2));
            //max num of nodex;
            // 2^(h+1)-1;
            int max_size = (int)Math.pow(2,h+1)-1;
    
            st= new int[max_size];
            constructSTUtil(nums,0,len-1,0);
        }
        
        private int constructSTUtil(int[] nums, int l , int r, int i)
        {
            if(l==r) 
            {
                st[i]=nums[l];
                return st[i];
            }
            int mid=(l+r)/2;
            st[i]=constructSTUtil(nums,l,mid,2*i+1)+constructSTUtil(nums,mid+1,r,2*i+2);
            return st[i];
        }
        
        public int sumRange(int i, int j) {
           return sumRangeUtil(0,len-1,i,j,0);
        }
        
        private int sumRangeUtil(int l, int r, int ql, int qr, int i)
        {
            if(ql<=l && qr>=r) return st[i];
            if(ql>r || qr<l) return 0;
            int mid=(l+r)/2;
            return sumRangeUtil(l,mid,ql,qr,i*2+1)+sumRangeUtil(mid+1,r,ql,qr,i*2+2) ;
        }
    }
    
    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * int param_1 = obj.sumRange(i,j);
     */
    

Log in to reply
 

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