codesingnal Code, Java

codesingnal Code

// brute force will be just do what it tells to.

final int MOD = 1000000007;

// sumInRange_array_Dp
int sumInRange_array_Dp(int[] nums, int [][] queries){
    int s [] = new int[nums.length];      // maintaining sum
    
    int sum  = 0;
    for(int i=0; i<s.length; i++){
        sum += nums[i];
        s[i] = sum;
    }
    System.out.println(Arrays.toString(s));
    
    long total = 0;
    for(int[] query : queries){
        int low = query[0];
        int high = query[1];
        
        int qsum = 0;
        if(low > 0)     qsum =  s[high] - s[low-1];
        if(low == 0)    qsum =  s[high];                   // for  edge case when low is 0
            
        total += qsum;
    }
    
    return Math.floorMod(total, MOD);
}

// ===========================================================================================

// sumInRange_SegmentTree

// better approach is segment tree  both    query &  update is (log n)
int sumInRange_SegmentTree(int[] nums, int[][] queries) {
    int nextPower = getNextPowerOf2(nums.length);
    int[] segTree = new int[nextPower * 2 -1];  // by default all 0's
    
    buildSegTree(nums, segTree, 0, nums.length -1, 0);
    // System.out.println(Arrays.toString(segTree));            // check the build tree
    
    
    long sum = 0;
    for(int [] query : queries){
        int qlow = query[0];
        int qhigh = query[1];
        
        long val = sumInRange_Query(segTree, qlow, qhigh, nums.length) ;
        sum = sum + val;
        
        System.out.println(val);
        System.out.println(sum);
    }
    
    System.out.println(MOD);
    return Math.floorMod(sum, MOD);
}

long sumInRange_Query(int[] segTree, int qlow, int qhigh, int input_len){
    return sumInRange_Query(segTree, qlow, qhigh, 0, input_len-1, 0);
}

long sumInRange_Query(int[] segTree, int qlow, int qhigh, int low, int high, int root){
    // 3 cases to resolve
    
    if(qlow <= low && qhigh >= high){ // full overlap
        return segTree[root];
    }
    
    
    if(qlow > high || qhigh < low){ // no overlap
        return 0; // as 0 will not do any change in the sum
    }
    
    // if partial overlap   -> get result from both side of the tree & then return
    int mid = (low + high)/ 2;
    
    long leftAns = sumInRange_Query(segTree, qlow, qhigh, low, mid , (root * 2 + 1));
    long rightAns = sumInRange_Query(segTree, qlow, qhigh, mid+1 , high, (root*2 + 2));
    
    long sum =  leftAns + rightAns;
    // System.out.println(sum);
    return sum;
}

void buildSegTree(int[] input, int[] segTree, int low, int high, int root ) {
    if(low == high){
        segTree[root] = input[low];
        return;
    }
    
    int mid = (low + high) / 2;
    
    // post order travarsal
    buildSegTree(input, segTree, low, mid, (root * 2 + 1));     // left
    buildSegTree(input, segTree, mid+1, high, (root * 2 + 2));  // right
    
    segTree[root] = segTree[root * 2 + 1] + segTree[root * 2 + 2]; 
}

int getNextPowerOf2(int n) {
    int val = 1;
    while(val < n){
        val = val << 1;   // left shift by one
    }
    return val;
}


run \| edit \| history \| help	0