{x}
blog image

Count of Range Sum

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.

Solution Explanation: Count of Range Sum

This problem asks to count the number of range sums within a given range [lower, upper] from an integer array. A range sum S(i, j) is the sum of elements from index i to j (inclusive). A brute-force approach would have O(n^2) time complexity, which is inefficient for large arrays. This solution uses a Binary Indexed Tree (BIT) and a clever approach to achieve better performance.

Algorithm:

  1. Prefix Sums: Calculate the prefix sums of the input array nums. The prefix sum array s is such that s[i] is the sum of nums[0] to nums[i-1]. This allows us to calculate any range sum S(i, j) efficiently as s[j+1] - s[i].

  2. Unique Values: Create a sorted array arr containing unique values from three sets of numbers:

    • The prefix sums s.
    • s[i] - lower (for checking the lower bound).
    • s[i] - upper (for checking the upper bound).

  3. Binary Indexed Tree: Use a Binary Indexed Tree (BIT) to efficiently count the number of elements within a range. The BIT allows for fast updates (adding an element) and queries (counting elements in a range).

  4. Iteration and Counting: Iterate through the prefix sum array s. For each prefix sum x:

    • Find the indices l and r in arr such that arr[l] = x - upper and arr[r] = x - lower. This is done efficiently using binary search (bisect_left in Python, lower_bound in C++, sort.SearchInts in Go, search function in TS and Java).
    • Use the BIT to query the number of elements in arr between indices l and r. This counts the number of range sums that fall within [lower, upper].
    • Update the BIT with the current prefix sum x.

  5. Return Count: The final count is the number of range sums that satisfy the condition.

Time Complexity Analysis:

  • Calculating prefix sums: O(n)
  • Sorting the unique values and creating arr: O(n log n) (due to sorting)
  • Iterating through s and updating/querying the BIT: O(n log n) (log n for each BIT operation)
  • Binary Search: O(log n) per search

Therefore, the overall time complexity is dominated by sorting and BIT operations, resulting in O(n log n).

Space Complexity Analysis:

The space complexity is determined by the size of the prefix sum array s, the sorted array arr, and the BIT. All three have a size proportional to n. Therefore, the space complexity is O(n).

Code Examples (Python, Java, C++, Go, TypeScript):

The code examples in the problem description demonstrate the algorithm in different programming languages. Each code implements a Binary Indexed Tree class and the main countRangeSum function following the algorithm steps. Note that the Java and C++ examples use slightly more optimized binary search implementations to find indices l and r in arr. The Go code leverages the standard library's sort.SearchInts for binary search. The TypeScript code provides a complete implementation along with a helper search function equivalent to bisect_left.