327. Count of Range Sum


Problem Description

The problem presents an integer array nums and asks to find the quantity of subarray sums that fall within the range [lower, upper] inclusive. A subarray sum, S(i, j), is the sum of elements from the i-th to the j-th element, where i and j are indices of the array with the condition that i <= j.

Intuition

To solve this problem, a direct approach would involve checking all possible subarrays and their sums, which would be inefficient and lead to a high time complexity. Instead, we consider using data structures like Binary Indexed Trees (BIT) or Segment Trees to optimize the process.

The intuition behind using a Binary Indexed Tree in this solution is that we can efficiently update frequencies and query cumulative frequencies of different sums that we encounter.

Here's what we do step-by-step, simplified:

  1. We first create the prefix sums of the array. By doing this, we can find the sum of any subarray using subtraction of two prefix sums.
  2. Then we need to discretize the data, meaning we map the prefix sums to a new set of integers that are tightly packed. This is necessary because Binary Indexed Trees work with indices and we need to use indices to represent the prefix sums and differences like x - lower and x - upper.
  3. We initialize a Binary Indexed Tree to keep track of the number of times a particular prefix sum appears.
  4. We iterate through the prefix sums, and for each sum, we find the boundaries (l and r) of sums that satisfy the lower and upper requirements by searching the discretized values.
  5. We query BIT by these boundaries to find out how many prefix sums fall within our desired range.
  6. Finally, we update the BIT with the current prefix sum to include it in our future queries.
  7. The final answer is the total number of times we found subarray sums that fell within [lower, upper], accumulated throughout the iteration.

By doing this, we greatly reduce the number of operations needed as compared to the brute force approach. Each update and query in the BIT takes logarithmic time to complete, which makes the solution much more efficient.

Learn more about Segment Tree, Binary Search, Divide and Conquer and Merge Sort patterns.

Solution Approach

The solution employs a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to efficiently compute the frequencies of the cumulative sums encountered. A BIT provides two significant operations: update and query, both of which operate in O(log n) time, where n is the number of elements. Understanding how BIT works are essential to grasp the solution's approach.

The update function is used to add a value to an element in the binary indexed tree, which in this context represents incrementing the count of a particular prefix sum. The query function is used to get the cumulative frequency up to an index, which helps us count the number of sums that fall within our desired range.

Here's a closer look at the implementation steps:

  1. We calculate all prefix sums of nums and store them in s. The prefix sum up to index i is the sum of all elements from the beginning of the array up to and including i. The initial prefix sum, S(0, -1), is 0. This is useful because a subarray sum S(i, j) can be easily calculated as s[j] - s[i-1].

  2. Then, we discretize our sums because BITs handle operations based on indices. We create an arr that consists of the unique values that our prefix sum might be subtracted by lower and upper (as x - lower and x - upper), as well as the prefix sums themselves.

  3. We create a Binary Indexed Tree tree based on the length of the arr which now contains all the unique values that are relevant for querying the number of sums within the [lower, upper] range.

  4. As we iterate through each prefix sum x in s, we determine l and r such that x - upper <= l and x - lower >= r. We identify the indices l and r in arr which the sums that fall in [lower, upper] will be between. We use binary search (bisect_left) since arr is sorted.

  5. Then, we query the Binary Indexed Tree between l and r to find out how many prefix sums we’ve encountered fall within our desired range. This step essentially tells us the count of subarray sums ending at the current index which are within the range [lower, upper].

  6. After querying, we increment the frequency count of the current prefix sum in the BIT so it could be used to find the range counts of subsequent subarray sums.

  7. We continue to sum these counts into an accumulator, ans, that will ultimately contain the total count of valid range sums that satisfy the problem's condition.

  8. Finally, we return ans which represents the number of subarray sums inside the range [lower, upper].

Through the usage of BIT and an ordered set of values, the implemented solution optimizes from a brute-force approach with potentially quadratic time complexity O(n^2) to a more efficient O(n log n) time complexity, where n is the length of the input list nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the array nums = [1, 2, -1] and we want to find the number of subarray sums within the range [1, 2].

  1. Calculate Prefix Sums: We begin by calculating the prefix sums s:

    1idx  0   1    2    3
    2s    0   1    3    2

    The prefix sums have an extra 0 at the start to handle subarrays that begin at the start of the array.

  2. Discretize Sums: We prepare to discretize the data by creating an array arr which includes all prefix sums, and each prefix sum subtracted by lower and upper:

    1original sums (s):     0,  1,  3,  2
    2subtract lower (1):   -1,  0,  2,  1
    3subtract upper (2):   -2, -1,  1,  0
    4combined (arr):       -2, -1,  0,  1,  2,  3

    After sorting and removing duplicates, we get arr = [-2, -1, 0, 1, 2, 3].

  3. Initialize BIT: A Binary Indexed Tree tree is initialized to track frequencies of these sums.

  4. Iterate Prefix Sums: For each x in s, we find the range [l, r] for sums between [lower, upper] as discrete indices in arr:

    1For x = 0: l = index of 0 - 2 (-2) = 0, r = index of 0 - 1 (-1) = 1
    2For x = 1: l = index of 1 - 2 (-1) = 1, r = index of 1 - 1 (0)  = 2
    3For x = 3: l = index of 3 - 2 (1)  = 3, r = index of 3 - 1 (2)  = 4
    4For x = 2: l = index of 2 - 2 (0)  = 2, r = index of 2 - 1 (1)  = 3
  5. BIT Queries: Initially, our BIT is empty so querying it gives 0, which is expected as no subarrays have been processed.

  6. BIT Updates: We update BIT with each prefix sum as we iterate:

    1Update with 0: tree now stores frequency of sum 0 as index 2.
    2Update with 1: tree now stores frequency of sum 1 as index 3.
    3Update with 3: tree now stores frequency of sum 3 as index 5.
    4Update with 2: tree now stores frequency of sum 2 as index 4.
  7. Query and Update: With each iteration, after querying, the BIT is updated:

    • When processing x = 0, there are no sums [1, 2] yet. Query result is 0 for this prefix. Update BIT with 0.
    • When processing x = 1, the previous sum 0 is within [1-2]=[1,0], so we count 1. Update BIT with 1.
    • When processing x = 3, the previous sums (0, 1) contributes to count, as both are within [3-2, 3-1]=[1,2], we count 1 more for the sum (1) + the existing count 1 = 2. Update BIT with 3.
    • When processing x = 2, sums (0, 1, 3) contributes to count, as (3) is the only within [2-2, 2-1]=[0,1], which is our initial sum, we just count 1 more for a total of 3. Update BIT with 2.
  8. Accumulate Answer: As we iterate, we keep a running sum ans:

    1ans = 0 + 1 + 1 (from prefix sum 3) + 1 (from prefix sum 2) = 3

    This gives us our final answer: 3. There are three subarrays whose sums are within the range [1, 2]: [1], [2], and [1, 2, -1].

Thus, the steps of calculating prefix sums, discretizing the data, initializing and updating the BIT, querying for count of subarray sums within [lower, upper], and maintaining the cumulative count lead to an efficient computation of the desired result.

Solution Implementation

1from itertools import accumulate
2from bisect import bisect_left
3
4# Define a class for Binary Indexed Tree (Fenwick Tree) data structure.
5class BinaryIndexedTree:
6    # Initialize the Binary Indexed Tree with `size` elements.
7    def __init__(self, size):
8        self.size = size
9        self.tree = [0] * (size + 1)
10
11    # Update the tree by adding a value `val` to the element at index `index`.
12    def update(self, index, val):
13        # Propagate the update up the tree.
14        while index <= self.size:
15            self.tree[index] += val
16            index += index & -index
17
18    # Query the cumulative sum from index 1 to `index`.
19    def query(self, index):
20        sum_ = 0
21        # Aggregate the sums.
22        while index > 0:
23            sum_ += self.tree[index]
24            index -= index & -index
25        return sum_
26
27
28# Solution class to solve the problem.
29class Solution:
30    def countRangeSum(self, nums, lower, upper):
31        # Compute the prefix sums of the input array `nums`.
32        prefix_sums = list(accumulate(nums, initial=0))
33        # Flatten and sort the unique sums for tree construction.
34        sorted_arr = sorted(set(x for sum_ in prefix_sums for x in (sum_, sum_ - lower, sum_ - upper)))
35        # Initialize the Binary Indexed Tree with the length of the sorted unique sums.
36        tree = BinaryIndexedTree(len(sorted_arr))
37        count = 0  # Initialize the count of ranges.
38      
39        # Iterate over the prefix sums.
40        for sum_ in prefix_sums:
41            # Find the indices for the current sum minus the upper and lower bounds.
42            # +1 because our BIT is 1-indexed.
43            left = bisect_left(sorted_arr, sum_ - upper) + 1
44            right = bisect_left(sorted_arr, sum_ - lower) + 1
45            # Calculate the number of sums in the range [lower, upper].
46            count += tree.query(right) - tree.query(left - 1)
47            # Update the BIT for the current prefix sum.
48            tree.update(bisect_left(sorted_arr, sum_) + 1, 1)
49      
50        # Return the total count of sums in the range.
51        return count
52
1import java.util.Arrays;
2
3// A class representing a Binary Indexed Tree (also known as a Fenwick Tree).
4class BinaryIndexedTree {
5    private final int size;  // Size of the array
6    private final int[] tree;  // The tree represented as an array
7
8    // Constructor to initialize the tree array with a given size.
9    public BinaryIndexedTree(int size) {
10        this.size = size;
11        this.tree = new int[size + 1];
12    }
13
14    // Update the tree with a value at a specific index.
15    public void update(int index, int value) {
16        while (index <= size) {
17            tree[index] += value;
18            index += index & -index;
19        }
20    }
21
22    // Query the cumulative frequency up to a given index.
23    public int query(int index) {
24        int sum = 0;
25        while (index > 0) {
26            sum += tree[index];
27            index -= index & -index;
28        }
29        return sum;
30    }
31}
32
33// A solution class containing the method to count the range sum.
34class Solution {
35    // Main method to count the number of range sums that lie in [lower, upper].
36    public int countRangeSum(int[] nums, int lower, int upper) {
37        int n = nums.length;
38        long[] prefixSums = new long[n + 1];  // Array to hold prefix sums.
39        for (int i = 0; i < n; i++) {
40            prefixSums[i + 1] = prefixSums[i] + nums[i];
41        }
42
43        // Create a sorted array that will hold unique values needed for the Binary Indexed Tree.
44        long[] sortedValues = new long[n * 3 + 3];
45        for (int i = 0, j = 0; i <= n; i++, j += 3) {
46            sortedValues[j] = prefixSums[i];
47            sortedValues[j + 1] = prefixSums[i] - lower;
48            sortedValues[j + 2] = prefixSums[i] - upper;
49        }
50        Arrays.sort(sortedValues);
51        int uniqueCount = 0;  // Count of unique elements.
52        // Filter out duplicates to retain only unique elements.
53        for (int i = 0; i < sortedValues.length; i++) {
54            if (i == 0 || sortedValues[i] != sortedValues[i - 1]) {
55                sortedValues[uniqueCount++] = sortedValues[i];
56            }
57        }
58
59        // Creating a Binary Indexed Tree for the range of unique elements.
60        BinaryIndexedTree bit = new BinaryIndexedTree(uniqueCount);
61        int result = 0;  // Initialize the result.
62        for (long sum : prefixSums) {
63            int leftIndex = search(sortedValues, uniqueCount, sum - upper);
64            int rightIndex = search(sortedValues, uniqueCount, sum - lower);
65            result += bit.query(rightIndex) - bit.query(leftIndex - 1);
66            bit.update(search(sortedValues, uniqueCount, sum), 1);
67        }
68        return result;
69    }
70
71    // Binary search helper method to find the index of a given value.
72    private int search(long[] values, int right, long target) {
73        int left = 0;
74        while (left < right) {
75            int mid = (left + right) >> 1;  // Equivalent to dividing by 2.
76            if (values[mid] >= target) {
77                right = mid;
78            } else {
79                left = mid + 1;
80            }
81        }
82        return left + 1;  // Returns the index in the BIT, which is 1-based.
83    }
84}
85
1#include <vector>
2#include <algorithm>
3
4class BinaryIndexedTree {
5public:
6    // Constructor initializes the binary indexed tree with a given size
7    explicit BinaryIndexedTree(int size)
8        : treeSize(size), tree(size + 1, 0) {}
9
10    // Updates the tree at position index by value
11    void Update(int index, int value) {
12        while (index <= treeSize) {
13            tree[index] += value;
14            index += index & -index; // Move index to the next parent node
15        }
16    }
17
18    // Queries the cumulative frequency up to position index
19    int Query(int index) {
20        int sum = 0;
21        while (index > 0) {
22            sum += tree[index];
23            index -= index & -index; // Move index to the previous element
24        }
25        return sum;
26    }
27
28private:
29    int treeSize;
30    std::vector<int> tree;
31};
32
33class Solution {
34public:
35    // Counts the number of range sums that lie in [lower, upper] inclusive
36    int countRangeSum(std::vector<int>& nums, int lower, int upper) {
37        using ll = long long;
38        int n = nums.size();
39        std::vector<ll> prefixSums(n + 1, 0);
40      
41        // Compute prefix sums
42        for (int i = 0; i < n; ++i) {
43            prefixSums[i + 1] = prefixSums[i] + nums[i];
44        }
45      
46        // Temporary array to store all values needed for discretization
47        std::vector<ll> allValues;
48        for (ll s : prefixSums) {
49            allValues.push_back(s);
50            allValues.push_back(s - lower);
51            allValues.push_back(s - upper);
52        }
53      
54        // Sort and remove duplicates to discretize values
55        std::sort(allValues.begin(), allValues.end());
56        allValues.erase(std::unique(allValues.begin(), allValues.end()), allValues.end());
57
58        // Create a binary indexed tree with size equal to the number of unique values
59        BinaryIndexedTree bit(allValues.size());
60        int answer = 0;
61      
62        for (ll s : prefixSums) {
63            int leftIndex = std::lower_bound(allValues.begin(), allValues.end(), s - upper) - allValues.begin() + 1;
64            int rightIndex = std::lower_bound(allValues.begin(), allValues.end(), s - lower) - allValues.begin() + 1;
65
66            // Query the range [leftIndex, rightIndex] and update the answer
67            answer += bit.Query(rightIndex) - bit.Query(leftIndex - 1);
68
69            // Update the bit tree with current prefix sum index
70            bit.Update(std::lower_bound(allValues.begin(), allValues.end(), s) - allValues.begin() + 1, 1);
71        }
72
73        return answer;
74    }
75};
76
1// Sizes for the BIT and original array
2let bitSize: number;
3let arraySize: number;
4
5// BIT data structure as an array
6let bitData: number[];
7
8// Function to initialize the BIT with a given size
9function initializeBIT(size: number): void {
10    bitSize = size;
11    bitData = Array(bitSize + 1).fill(0);
12}
13
14// Function to update the BIT for an index with a value
15function updateBIT(index: number, value: number): void {
16    while (index <= bitSize) {
17        bitData[index] += value;
18        index += index & -index;
19    }
20}
21
22// Function to query the BIT up to a given index
23function queryBIT(index: number): number {
24    let sum = 0;
25    while (index > 0) {
26        sum += bitData[index];
27        index -= index & -index;
28    }
29    return sum;
30}
31
32// Function to calculate the count of range sums within the given bounds
33function countRangeSum(nums: number[], lower: number, upper: number): number {
34    arraySize = nums.length;
35    const prefixSums = Array(arraySize + 1).fill(0);
36
37    // Calculate prefix sums of the original array
38    for (let i = 0; i < arraySize; ++i) {
39        prefixSums[i + 1] = prefixSums[i] + nums[i];
40    }
41
42    // Prepare arrays for discretization
43    let arr: number[] = Array((arraySize + 1) * 3);
44    for (let i = 0, j = 0; i <= arraySize; ++i, j += 3) {
45        arr[j] = prefixSums[i];
46        arr[j + 1] = prefixSums[i] - lower;
47        arr[j + 2] = prefixSums[i] - upper;
48    }
49
50    // Sort and remove duplicates
51    arr.sort((a, b) => a - b);
52    let m = 0;
53    for (let i = 0; i < arr.length; ++i) {
54        if (i === 0 || arr[i] !== arr[i - 1]) {
55            arr[m++] = arr[i];
56        }
57    }
58    arr = arr.slice(0, m);
59
60    // Initialize BIT
61    initializeBIT(m);
62  
63    let answer = 0;
64    for (const x of prefixSums) {
65        const left = binarySearch(arr, x - upper);
66        const right = binarySearch(arr, x - lower);
67        answer += queryBIT(right) - queryBIT(left - 1);
68        updateBIT(binarySearch(arr, x), 1);
69    }
70    return answer;
71}
72
73// Function to perform binary search
74function binarySearch(nums: number[], target: number): number {
75    let left = 0;
76    let right = nums.length; // Note: 'r' was renamed to 'right'.
77    while (left < right) {
78        const mid = (left + right) >> 1;
79        if (nums[mid] >= target) {
80            right = mid;
81        } else {
82            left = mid + 1;
83        }
84    }
85    return left + 1; // BIT indices are 1-based.
86}
87

Time and Space Complexity

Time Complexity

The time complexity of the countRangeSum function is determined by several factors:

  1. Calculating the prefix sums of the nums array: The accumulate function is used to calculate the prefix sums which takes O(n) time where n is the length of the nums array.

  2. Preparing the arr array for the Binary Indexed Tree (BIT): The set comprehension and sorting takes O(n log n) time, as it creates a set with potentially 3n elements (in the worst case, every expression in the set comprehension is unique) and then sorts it.

  3. Insertions into the BIT: The loop runs for each element of the calculated prefix sums array s. For each element, two operations take place: update and query. The update operation has a complexity of O(log m) where m is the length of the arr array, which represents the number of unique values among all the prefix sums and their respective lower and upper sums. The same goes for the query operation. Since there are n elements, the overall complexity of this part is O(n log m).

Combining these together, the total time complexity is O(n log n) + O(n log m). Since m is derived from n, the order of growth is bounded by the number of operations linked to n, which results in O(n log n).

Space Complexity

The space complexity is determined by:

  1. The s array for storing the prefix sums, which takes O(n) space.

  2. The arr array for storing unique values for BIT, which in the worst case can store 3n elements (if all prefix sums and the respective lower and upper sums are unique), taking O(n) space (since they are values derived from the original input nums).

  3. The c array inside the BIT instance, which also takes O(m) space. As with time complexity, m is related to n and the space required is proportional to the number of unique elements that can be from the original array.

Therefore, the total space complexity of the entire operation is O(n) as it scales linearly with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used in a depth first search?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄