Sponsored
Sponsored
This approach utilizes a simple array to store the elements, implementing updates directly and calculating the range sum by iterating through the specified range.
The update operation runs in constant time as it simply replaces a value at a given index. However, the sum operation runs in O(n) time, where n is the size of the query range, as it sums elements one by one.
Time Complexity: O(1) for update, O(n) for sumRange where n is the number of elements between left and right.
Space Complexity: O(1) - additional space usage is minimal.
1public class NumArray {
2 private int[] nums;
3
4 public NumArray(int[] nums) {
5 this.nums = nums;
6 }
7
8 public void Update(int index, int val) {
9 nums[index] = val;
10 }
11
12 public int SumRange(int left, int right) {
13 int sum = 0;
14 for (int i = left; i <= right; i++) {
15 sum += nums[i];
16 }
17 return sum;
18 }
19}The C# approach employs an integer array to model the numbers. The Update method updates a particular index with the specified value, while SumRange determines the aggregate sum through a straightforward loop over the intended range.
A segment tree provides a more efficient solution for this problem, reducing the time complexity for both update and sum operations. Segment trees are ideal for scenarios where an array undergoes frequent updates and queries, as they allow modifications and range sum queries to be done in logarithmic time.
Time Complexity: O(log n) for both update and sumRange.
Space Complexity: O(n) for the segment tree storage.
1#include <vector>
2using namespace std;
3
4class NumArray {
5private:
vector<int> tree;
int n;
public:
NumArray(vector<int>& nums) {
n = nums.size();
tree.resize(2 * n);
buildSegmentTree(nums);
}
void buildSegmentTree(vector<int>& nums) {
for (int i = 0; i < n; i++) {
tree[n + i] = nums[i];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
void update(int index, int val) {
index += n;
tree[index] = val;
while (index > 1) {
index /= 2;
tree[index] = tree[2 * index] + tree[2 * index + 1];
}
}
int sumRange(int left, int right) {
left += n;
right += n;
int sum = 0;
while (left <= right) {
if (left % 2 == 1) sum += tree[left++];
if (right % 2 == 0) sum += tree[right--];
left /= 2;
right /= 2;
}
return sum;
}
};In C++ implementation, a segment tree is constructed using a vector. The buildSegmentTree initializes the tree, and the update function updates the value as well as the related nodes in the tree. The sumRange method calculates the sum of a given range efficiently using tree traversal.