327. 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.

 

Solutions

Solution: Binary Indexed Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
const countRangeSum = function (nums, lower, upper) {
  const n = nums.length;
  const prefixSum = new Array(n + 1).fill(0);

  for (let index = 0; index < n; index++) {
    prefixSum[index + 1] = prefixSum[index] + nums[index];
  }

  const sortedPrefixSum = Array.from(new Set(prefixSum)).sort((a, b) => a - b);
  const bit = Array.from({length: sortedPrefixSum.length + 2}).fill(0);

  const getIndex = value => {
    let left = 0;
    let right = sortedPrefixSum.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      sortedPrefixSum[mid] >= value ? (right = mid - 1) : (left = mid + 1);
    }
    return left;
  };

  const updateBit = index => {
    while (index < bit.length) {
      bit[index] += 1;
      index += index & -index;
    }
  };

  const queryBit = index => {
    let count = 0;

    while (index > 0) {
      count += bit[index];
      index -= index & -index;
    }
    return count;
  };

  let result = 0;

  for (const sum of prefixSum) {
    const leftIndex = getIndex(sum - upper);
    const rightIndex = getIndex(sum - lower + 1);

    result += queryBit(rightIndex) - queryBit(leftIndex);
    updateBit(getIndex(sum) + 1);
  }
  return result;
};