October 5, 2023
1. Problem Introduction
The Range Sum Query 3 problem is a type of problem that you often encounter in algorithm problem-solving processes, especially demonstrating efficiency when calculating sums of large datasets.
This problem deals with methods to quickly calculate the sum of a specific interval through queries.
Computing the range sum algorithmically is particularly useful for database-related problems.
Today, we will analyze various techniques to solve this problem and try to solve it using JavaScript.
2. Problem Description
Given an array A with length N, when a positive integer query M is provided,
each query consists of two integers i and j, and we need to find the value of
A[i] + A[i+1] + ... + A[j]. There can be up to 100,000 queries, and each number in A can be up to 1,000,000.
In other words, we need to efficiently calculate the sums of ranges based on the given array A and the queries.
3. Problem Solving Strategy
To solve the range sum problem, we will use two main methods.
– First, the basic method which uses a double loop to calculate the sum for each query.
– Second, a method that pre-computes the range sums and quickly derives results during the queries.
In particular, the second method allows us to obtain query results in O(1) time through O(N) preprocessing.
Thus, this will help us solve the problem more efficiently.
4. Basic Method (O(N) x M)
This method is very intuitive, but its time complexity is O(N * M).
The implementation of this approach is as follows.
function simpleRangeSum(A, queries) {
const results = [];
for (let [i, j] of queries) {
let sum = 0;
for (let k = i; k <= j; k++) {
sum += A[k];
}
results.push(sum);
}
return results;
}
This code calculates the sum at the respective index for each query by iterating through it. However, under the constraints of the problem,
this method is inefficient. Therefore, we need to move on to a more efficient approach.
5. Efficient Method (O(N) + O(1) per Query)
In exploring the efficient method, we start by creating an array to store the range sums of the original array.
First, the process of creating the range sum array is needed. Once the range sum array is created,
the result of each query can be obtained simply by taking the difference of two cumulative sums.
function prefixSum(A) {
const prefix = new Array(A.length + 1).fill(0);
for (let i = 0; i < A.length; i++) {
prefix[i + 1] = prefix[i] + A[i];
}
return prefix;
}
function rangeSum(A, queries) {
const prefix = prefixSum(A);
const results = [];
for (let [i, j] of queries) {
results.push(prefix[j + 1] - prefix[i]);
}
return results;
}
In the above implementation, the prefixSum function calculates the cumulative sums for the entire dataset and stores them in the prefix array.
After that, each query can derive the range sum in O(1) time. This method is
very efficient as it can process queries in O(N) + O(1).
6. Code Explanation
Analyzing the code above, we first create an empty array with one more than the length of the array in the prefixSum function,
and compute the cumulative sums for each index of this array. Through this cumulative sum array,
the rangeSum function quickly calculates the range sum by taking the starting index i and ending index j from the given queries.
Now, when considering the large number of queries, we need to be mindful of the time complexity,
as the solution above is very efficient in this regard.
The unnecessary loops during the processing of each query were key,
and deriving the results through this process improved performance.
7. Example Test
Let’s test the code above with an example.
The array A = [1, 2, 3, 4, 5] and the queries are
[[0, 2], [1, 3], [2, 4]].
const A = [1, 2, 3, 4, 5];
const queries = [[0, 2], [1, 3], [2, 4]];
const results = rangeSum(A, queries);
console.log(results); // [6, 9, 12]
The results of the above test correctly yield the cumulative sums for each query. By testing, we can confirm that our code is functioning accurately,
which is an essential process for ensuring correctness.
8. Conclusion
The Range Sum Query 3 problem is an excellent example that demonstrates a variety of algorithm problem-solving skills.
Solving the range sum problem through preprocessing is commonly used in everyday data processing tasks.
Based on what we learned today, I hope you have developed the ability to solve similar problems and gained insight on how to structure algorithms when faced with problems.
I encourage you to continue building your problem-solving experience through JavaScript.