Hello! In this tutorial, we will explore the “range sum” problem, which is frequently featured in JavaScript coding tests, in depth. The range sum problem involves efficiently calculating the sum of a specific range within a given sequence, and it can be solved using various optimization techniques. The range sum problems we will discuss can be particularly time-consuming when the size of the array is large, so it’s essential to design a more efficient algorithm.<\/p>\n
Here is a problem related to range sums:<\/p>\n
An array of integers For example, if the array is To solve this problem efficiently, simply using loops to calculate the sum for each range is not appropriate. The reason is that in the worst-case scenario, it would have a time complexity of O(N * M), which can lead to exponential time increases if the size of the data is large. Instead, we can use a more effective approach.<\/p>\n One way to solve the range sum problem is to create a Prefix Sum Array. Using a prefix sum array allows us to calculate the sum of a range in O(1) time. The definition of the prefix sum array is as follows:<\/p>\n Thus, the sum of the range This allows us to compute the range sum for each pair in O(1) time. The overall time complexity of the algorithm is O(N + M), where N is the size of the array and M is the number of pairs.<\/p>\n Now, let’s implement the JavaScript code that solves the problem using the prefix sum array.<\/p>\n The above code is a program that efficiently calculates and outputs the range sum for each query based on the given array and queries. As a result, it can quickly compute range sums and does not suffer performance degradation depending on the size of the array or the number of queries.<\/p>\n The time complexity of this algorithm is as follows:<\/p>\n As a result, the overall time complexity is O(N + M), which is very efficient.<\/p>\n Now we have learned how to efficiently solve the range sum problem using a prefix sum array. Since range sum problems are frequently featured topics in coding tests, understanding and utilizing optimization techniques like this is important. Practice solving various types of problems!<\/p>\n Try practicing the following variant problems:<\/p>\narr<\/code> and several pairs of integers (l, r)<\/code> are given. Each pair represents the starting point l<\/code> and endpoint r<\/code> of a range. Write a program to calculate the sum of arr[l] + arr[l + 1] + ... + arr[r]<\/code>. The length of the array and the number of pairs are as follows:<\/p>\n\n
arr.length<\/code> \u2264 106<\/sup><\/li>\nl<\/code>, r<\/code> \u2264 arr.length<\/code><\/li>\narr[i]<\/code> \u2264 109<\/sup><\/li>\n<\/ul>\narr = [1, 2, 3, 4, 5]<\/code> and the pair (1, 3)<\/code> is given, the range sum is arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9<\/code>.<\/p>\nApproach to the Problem<\/h2>\n
Preprocessing Technique: Prefix Sum Array<\/h3>\n
prefix[i] = arr[0] + arr[1] + ... + arr[i-1]<\/code><\/pre>\n(l, r)<\/code> can be calculated as:<\/p>\nsum(l, r) = prefix[r + 1] - prefix[l]<\/code><\/pre>\nImplementation Steps<\/h2>\n
Step 1: Create the Prefix Sum Array<\/h3>\n
\nfunction createPrefixSum(arr) {\n const prefix = new Array(arr.length + 1).fill(0);\n for (let i = 0; i < arr.length; i++) {\n prefix[i + 1] = prefix[i] + arr[i];\n }\n return prefix;\n}\n<\/code><\/pre>\nStep 2: Calculate the Range Sum<\/h3>\n
\nfunction rangeSum(prefix, l, r) {\n return prefix[r + 1] - prefix[l];\n}\n<\/code><\/pre>\nStep 3: Implement the Main Function<\/h3>\n
\nfunction calculateRangeSums(arr, queries) {\n const prefix = createPrefixSum(arr);\n const results = [];\n for (let [l, r] of queries) {\n results.push(rangeSum(prefix, l - 1, r - 1)); \/\/ 1-based to 0-based\n }\n return results;\n}\n\n\/\/ Example usage\nconst arr = [1, 2, 3, 4, 5];\nconst queries = [[1, 3], [2, 5], [0, 2]];\nconst results = calculateRangeSums(arr, queries);\nconsole.log(results); \/\/ [9, 14, 6]\n<\/code><\/pre>\nResults Analysis<\/h2>\n
Time Complexity<\/h3>\n
\n
Conclusion<\/h2>\n
Additional Practice Problems<\/h3>\n