# 1508. Range Sum of Sorted Subarray Sums
###### tags: `Leetcode` `Medium`
Link: https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/
## 思路
### 暴力法 $O(N^2)$ $O(N^2)$
把所有sum算出来 然后再把l到r的加起来
### Binary Search (TLE) $O((r-l)*NlogN)$ $O(1)$
找到从l到r所有的subarray sum然后加起来
## Code
### 暴力法 $O(N^2)$ $O(N^2)$

class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        int[] ans = new int[n*(n+1) / 2];
        int index = 0;
        for(int i = 0; i<n; i++){
            int sum = 0;
            for(int j = i; j<n; j++){
                sum += nums[j];
                ans[index++] = sum;
            }
        }
        
        Arrays.sort(ans);
        long result = 0;
        for(int i = left-1; i<right; i++){
            result += ans[i];
        }
        
        return (int)(result % 1000000007);
    }
}

### Binary Search (TLE) $O((r-l)*NlogN)$ $O(1)$

class Solution {
    int totalSum = 0;
    public int rangeSum(int[] nums, int n, int left, int right) {
        int mod = 1000000007;
        long ans = 0;
        for(int num:nums) totalSum += num;
        for(int i=left; i<=right; i++){
            ans = (ans+kthSum(nums, i))%mod;
        }
        return (int)(ans%mod);
    }
    private long kthSum(int[] nums, int k){
        int start=0, end=totalSum;
        while(start<end){
            int mid = start+(end-start)/2;
            if(smallerOrEqual(nums, mid)<k){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        return start;
    }
    private int smallerOrEqual(int[] nums, int sum){
        int l=0, r=0, curr=0, ans=0;
        while(r<nums.length){
            curr += nums[r];
            while(curr>sum){
                curr -= nums[l++];
            }
            ans += r-l+1;
            r++;
        }
        return ans;
    }
}