0327. Count of Range Sum

https://leetcode.com/problems/count-of-range-sum

Description

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Example 1:

**Input:** nums = [-2,5,-1], lower = -2, upper = 2
**Output:** 3
**Explanation:** The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

**Input:** nums = [0], lower = 0, upper = 0
**Output:** 1

Constraints:

• 1 <= nums.length <= 105

• -231 <= nums[i] <= 231 - 1

• -105 <= lower <= upper <= 105

• The answer is guaranteed to fit in a 32-bit integer.

ac

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        // edge cases

        long[] presum = new long[nums.length+1];
        for (int i = 1; i < presum.length; i++) presum[i] = presum[i-1] + nums[i-1];
        long[] copy = Arrays.copyOf(presum, presum.length);
        Arrays.sort(copy);
        long[] sortedPresum = new long[copy.length];
        for (int i = 0; i < sortedPresum.length; i++) sortedPresum[i] = copy[copy.length-1-i];


        int[] bit = new int[presum.length + 1];

        int count = 0;
        for (int i = 0; i < presum.length; i++) {
            count += getSum(bit, getUpperRank(sortedPresum, (presum[i] - upper)));
            count -= getSum(bit, getLowerRank(sortedPresum, presum[i] - lower)-1);
            update(bit, getUpperRank(sortedPresum, presum[i]));
        }

        return count;
    }
    private void update(int[] bit, int i) {
        while (i < bit.length) {
            bit[i]++;
            i += i & (-i);
        }
    }
    private int getSum(int[] bit, int i) {
        int res = 0;
        while (i > 0) {
            res += bit[i];
            i -= i & (-i);
        }
        return res;
    }
    private int getUpperRank(long[] nums, long val) {
        int l = 0, r = nums.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= val) r = mid;
            else l = mid;
        }
        // return nums[l] >= val ? l + 1 : l;

        int res = -1;
        if (nums[r] > val) {
            res = r;
        } else if (nums[r] == val) {
            res = nums[l] == val ? l : r;
        } else {
            if (nums[l] >= val) res = l;
            else res = l - 1;
        }

        return res + 1;
    }
    private int getLowerRank(long[] nums, long val) {
        int l = 0, r = nums.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= val) r = mid;
            else l = mid;
        }

        int res = -1;
        if (nums[l] <= val) {
            res = l;
        } else { // nums[l] > val
            if (nums[r] <= val) {
                res = r;
            } else {
                res = r+1;
            }
        }

        return res + 1;
    }
}

ac2: merge sort

class Solution {
    int count = 0;
    public int countRangeSum(int[] nums, int lower, int upper) {
        // edge cases

        long[] sum = new long[nums.length+1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }

        merge(sum, 0, sum.length - 1, lower, upper);

        return count;
    }

    private long[] merge(long[] nums, int start, int end, int lower, int upper) {
        // exit
        if (start == end) return new long[]{nums[start]};

        int mid = start + (end - start) / 2;
        long[] left = merge(nums, start, mid, lower, upper);
        long[] right = merge(nums, mid+1, end, lower, upper);

        long[] res = new long[end - start + 1];

        int l = 0, r = 0, i = 0;
        int lo = 0, hi = 0;
        while (l < left.length) {
            // extract info
            while (hi < right.length && right[hi] - left[l] <= upper) hi++;
            while (lo < right.length && right[lo] - left[l] <  lower) lo++;
            count += hi - lo;

            // merge
            while (r < right.length && right[r] < left[l]) res[i++] = right[r++];
            res[i++] = left[l++];
        }

        while (r < right.length) res[i++] = right[r++];

        return res;
    }
}