Untitled

import java.util.AbstractMap;

class Solution {
    int largestSubArraySumPossible = 0, smallestSubArraySumPossible = 0;

    // Returns count of subarrays that have 
    // sum <= target and their total sum.
    public Map.Entry<Integer, Long> subArraysWithSumLessThanOrEqualTo(int[] nums, int target){

        int  countOfSuchSubArrays = 0;
        Long totalSum = 0L;
        int  windowSum = 0;
        /* currSum intially stores sum of all UNIQUE subArrays in CURRENT WINDOW
        Note that we dont consider previous ITERATION unique subarrays 
        in current iteration.

        windowSum stores sum of current window only.

        Total sum stores sum of all currSums from all iterations.

        Once we pass given target, we shrink both currSum and windowSum
        
        Ex: 
        Iteration 1: Elements {1} -> unique subArrays -> {1} 
        -> currSum = 1, windowSum = sum(elements(left, right)) = sum(1) = 1
        Iteration 2: Elements {1, 2} -> unique subArrays -> {1, 2}, {2} 
        -> currSum = (1+2)+2 = 5, windowSum = sum(elements(left, right)) = sum(1+2) = 3
        Itr 3:  Elements {1, 2, 3} -> unique subArrays -> {3}, {2, 3}, {1, 2, 3} 
        -> currSum = (3 + (2+3) + (1+2+3)) = 14 */
        int currSum = 0;
        int n = nums.length;

        for (int left = 0, right = 0; right < n; ++right) {
            currSum += nums[right] * (right - left + 1);
            windowSum += nums[right]; 
            while (windowSum > target) {
            currSum -= windowSum;
            windowSum -= nums[left++];
            }
            countOfSuchSubArrays += right - left + 1;
            totalSum += currSum;
        }
        return new AbstractMap.SimpleEntry<>(Integer.valueOf(countOfSuchSubArrays), 
        Long.valueOf(totalSum));
    }

    public Long firstKSubarraysSum(int[] nums, int k){
        int start = smallestSubArraySumPossible, end = largestSubArraySumPossible;
        while(start < end){
            int mid = start + (end-start)/2;
            if(subArraysWithSumLessThanOrEqualTo(nums, mid).getKey().intValue() < k){
                start = mid + 1;
            }
            else{
                end = mid;
            }
        }
      Map.Entry<Integer, Long> map = subArraysWithSumLessThanOrEqualTo(nums, start);

      // When count != k, it means there are subarray(s) whose sum is equal to start
      Long totalOfFirstKSubarraysSum = map.getValue();
      int countOfSuchSubArrs = map.getKey().intValue();
      return totalOfFirstKSubarraysSum - start * (countOfSuchSubArrs - k);
    }

    public int rangeSum(int[] nums, int n, int left, int right) {
        int mod = (int) 1e9 + 7;
        int ans = 0;
        smallestSubArraySumPossible = nums[0];

        for(int i=0; i<n; i++){
            largestSubArraySumPossible+=nums[i];
            smallestSubArraySumPossible = Math.min(smallestSubArraySumPossible, nums[i]);
        }

        ans = (int)((firstKSubarraysSum(nums, right) % mod) - 
              (firstKSubarraysSum(nums, left-1) % mod));

        return ans%mod;
    }
}