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:
- 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.
- 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
andx - upper
. - We initialize a Binary Indexed Tree to keep track of the number of times a particular prefix sum appears.
- We iterate through the prefix sums, and for each sum, we find the boundaries (
l
andr
) of sums that satisfy thelower
andupper
requirements by searching the discretized values. - We query BIT by these boundaries to find out how many prefix sums fall within our desired range.
- Finally, we update the BIT with the current prefix sum to include it in our future queries.
- 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:
-
We calculate all prefix sums of
nums
and store them ins
. The prefix sum up to indexi
is the sum of all elements from the beginning of the array up to and includingi
. The initial prefix sum,S(0, -1)
, is0
. This is useful because a subarray sumS(i, j)
can be easily calculated ass[j] - s[i-1]
. -
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 bylower
andupper
(asx - lower
andx - upper
), as well as the prefix sums themselves. -
We create a Binary Indexed Tree
tree
based on the length of thearr
which now contains all the unique values that are relevant for querying the number of sums within the[lower, upper]
range. -
As we iterate through each prefix sum
x
ins
, we determinel
andr
such thatx - upper <= l
andx - lower >= r
. We identify the indicesl
andr
inarr
which the sums that fall in[lower, upper]
will be between. We use binary search (bisect_left
) sincearr
is sorted. -
Then, we query the Binary Indexed Tree between
l
andr
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]
. -
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.
-
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. -
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 EvaluatorExample 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]
.
-
Calculate Prefix Sums: We begin by calculating the prefix sums
s
:idx 0 1 2 3 s 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. -
Discretize Sums: We prepare to discretize the data by creating an array
arr
which includes all prefix sums, and each prefix sum subtracted bylower
andupper
:original sums (s): 0, 1, 3, 2 subtract lower (1): -1, 0, 2, 1 subtract upper (2): -2, -1, 1, 0 combined (arr): -2, -1, 0, 1, 2, 3
After sorting and removing duplicates, we get
arr = [-2, -1, 0, 1, 2, 3]
. -
Initialize BIT: A Binary Indexed Tree
tree
is initialized to track frequencies of these sums. -
Iterate Prefix Sums: For each
x
ins
, we find the range[l, r]
for sums between[lower, upper]
as discrete indices inarr
:For x = 0: l = index of 0 - 2 (-2) = 0, r = index of 0 - 1 (-1) = 1 For x = 1: l = index of 1 - 2 (-1) = 1, r = index of 1 - 1 (0) = 2 For x = 3: l = index of 3 - 2 (1) = 3, r = index of 3 - 1 (2) = 4 For x = 2: l = index of 2 - 2 (0) = 2, r = index of 2 - 1 (1) = 3
-
BIT Queries: Initially, our BIT is empty so querying it gives 0, which is expected as no subarrays have been processed.
-
BIT Updates: We update BIT with each prefix sum as we iterate:
Update with 0: tree now stores frequency of sum 0 as index 2. Update with 1: tree now stores frequency of sum 1 as index 3. Update with 3: tree now stores frequency of sum 3 as index 5. Update with 2: tree now stores frequency of sum 2 as index 4.
-
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.
- When processing
-
Accumulate Answer: As we iterate, we keep a running sum
ans
:ans = 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:
-
Calculating the prefix sums of the
nums
array: Theaccumulate
function is used to calculate the prefix sums which takesO(n)
time wheren
is the length of the nums array. -
Preparing the
arr
array for the Binary Indexed Tree (BIT): The set comprehension and sorting takesO(n log n)
time, as it creates a set with potentially3n
elements (in the worst case, every expression in the set comprehension is unique) and then sorts it. -
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. Theupdate
operation has a complexity ofO(log m)
wherem
is the length of thearr
array, which represents the number of unique values among all the prefix sums and their respective lower and upper sums. The same goes for thequery
operation. Since there aren
elements, the overall complexity of this part isO(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:
-
The
s
array for storing the prefix sums, which takesO(n)
space. -
The
arr
array for storing unique values for BIT, which in the worst case can store3n
elements (if all prefix sums and the respective lower and upper sums are unique), takingO(n)
space (since they are values derived from the original inputnums
). -
The
c
array inside the BIT instance, which also takesO(m)
space. As with time complexity,m
is related ton
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Want a Structured Path to Master System Design Too? Don’t Miss This!