\n Given an integer array Note that Your goal is to find an efficient method to calculate the range sum with a time complexity of O(log N) or O(1).\n <\/p>\n<\/div>\n \n The range sum problem can be solved in various ways, but an efficient approach is to use The basic idea is to precompute and store the sum for each index in the array. Here, \nThe \n Through the arr<\/code> and two integers left<\/code> and right<\/code>,
\n write a function to calculate the value of arr[left] + arr[left + 1] + ... + arr[right]<\/code>.<\/p>\narr<\/code> has a length constraint of 1 \u2264 arr.length<\/code> \u2264 100,000,
\n and each element is within the range of -10^9 \u2264 arr[i]<\/code> \u2264 10^9.<\/p>\nApproach to the Problem<\/h2>\n
\n Prefix Sum<\/strong>. With prefix sums, you can calculate the sum for the given range
\n [left, right]<\/code> in O(1) time complexity.<\/p>\n
\n With this, the sum of a specific range can be calculated as follows.<\/p>\nsum(left, right) = prefixSum[right] - prefixSum[left - 1]<\/code><\/p>\nprefixSum[i]<\/code> is the sum from the start of the array to the i<\/code>-th element.
\n This method has a time complexity of O(N) since it involves one traversal of the array, and afterwards, each range sum can be computed in O(1).\n <\/p>\nImplementation<\/h2>\n
Code<\/h3>\n
\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nclass SubarraySum {\npublic:\n SubarraySum(const vector<int>& arr) {\n int n = arr.size();\n prefixSum.resize(n + 1);\n prefixSum[0] = 0; \/\/ prefixSum[0] is initialized to 0.\n \n for (int i = 1; i <= n; i++) {\n prefixSum[i] = prefixSum[i - 1] + arr[i - 1];\n }\n }\n\n int getSum(int left, int right) {\n return prefixSum[right] - prefixSum[left - 1];\n }\n\nprivate:\n vector<int> prefixSum; \/\/ Array to store the prefix sum.\n};\n\nint main() {\n int n; \/\/ Size of the array\n cout << \"Enter the size of the array: \";\n cin >> n;\n vector<int> arr(n);\n cout << \"Enter the elements of the array: \";\n for (int i = 0; i < n; i++) {\n cin >> arr[i];\n }\n\n SubarraySum subarray(arr);\n\n int left, right;\n cout << \"Enter the left boundary of the range (starting from 1): \";\n cin >> left;\n cout << \"Enter the right boundary of the range: \";\n cin >> right;\n\n int result = subarray.getSum(left, right);\n cout << \"The sum of the range [\" << left << \", \" << right << \"] is: \" << result << endl;\n\n return 0;\n}\n <\/pre>\nCode Explanation<\/h2>\n
Class Definition<\/h3>\n
SubarraySum<\/code> class provides the functionality to calculate range sums.
\n The constructor of this class initializes the prefix sum based on the array elements provided.
\n It defines a variable n<\/code> to store the size of the array and creates the prefixSum<\/code> array (including one for [0]).\n <\/p>\nPrefix Sum Calculation<\/h3>\n
for<\/code> loop inside the constructor, the array is traversed to store
\n the sums up to each index in the prefixSum<\/code> array.
\n This is unique because it has a size of one more than the array size, starting from the first index.\n <\/p>\nRange Sum Calculation<\/h3>\n