Sponsored
Sponsored
The key idea in this approach is to use a prefix sum array. We precompute cumulative sums such that each element at index i in this prefix array contains the sum of all elements in the nums array from index 0 to i. The sum of a subarray can then be computed in constant time using the relation: sumRange(left, right) = prefixSum[right] - prefixSum[left-1]. This pre-computation allows each query to be answered in O(1) time after O(n) pre-computation.
Time Complexity: O(n) for precomputing the prefix sums, O(1) for each range query.
Space Complexity: O(n) for storing the prefix sums.
1class NumArray {
2 private int[] prefixSums;
3 public NumArray(int[] nums) {
4 prefixSums = new int[nums.length + 1];
5 for (int i = 0; i < nums.length; i++) {
6 prefixSums[i + 1] = prefixSums[i] + nums[i];
7 }
8 }
9
10 public int sumRange(int left, int right) {
11 return prefixSums[right + 1] - prefixSums[left];
12 }
13}This Java approach stores prefix sums in an instance variable. The constructor calculates the prefix sums initially, and sumRange method retrieves the sum of numbers within the given range efficiently.
A Segment Tree is a data structure that allows efficient range query and update operations. It is particularly useful in scenarios where there are multiple queries of the dynamic array that could change over time. For sumRange queries, the segment tree helps to retrieve the sum in logarithmic time, and it can be further extended to handle updates if needed.
Time Complexity: O(n) for building the tree, O(log n) per query.
Space Complexity: O(n) for the segment tree.
1
class NumArray {
public:
std::vector<int> segmentTree;
int n;
NumArray(std::vector<int>& nums) {
n = nums.size();
segmentTree.resize(4 * n);
buildTree(nums, 0, n - 1, 0);
}
void buildTree(std::vector<int>& nums, int start, int end, int node) {
if (start == end) {
segmentTree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
buildTree(nums, start, mid, 2 * node + 1);
buildTree(nums, mid + 1, end, 2 * node + 2);
segmentTree[node] = segmentTree[2 * node + 1] + segmentTree[2 * node + 2];
}
}
int sumRange(int left, int right) {
return rangeSum(0, n - 1, 0, left, right);
}
int rangeSum(int start, int end, int node, int left, int right) {
if (right < start || left > end) return 0;
if (left <= start && end <= right) return segmentTree[node];
int mid = start + (end - start) / 2;
return rangeSum(start, mid, 2 * node + 1, left, right) +
rangeSum(mid + 1, end, 2 * node + 2, left, right);
}
};Using a Segment Tree, this C++ solution computes and stores partial sums at each tree node. This supports fast sumRange calculations by visiting only relevant nodes. Updates to elements can also be achieved efficiently.