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.
1class NumArray {
2 constructor(nums) {
3 this.nums = nums;
4 }
5
6 update(index, val) {
7 this.nums[index] = val;
8 }
9
10 sumRange(left, right) {
11 let sum = 0;
12 for (let i = left; i <= right; i++) {
13 sum += this.nums[i];
14 }
15 return sum;
16 }
17}In JavaScript, we establish a class structure to encapsulate the nums array. The update method alters the value at a designated index, and the sumRange function computes the sum through a basic iterative process.
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.
1class NumArray:
2 def __init__(
This Python solution utilizes a segment tree, which allows the program to efficiently handle the updates and sum queries. The tree is represented with a flat array. The buildSegmentTree constructively sets up the tree, update modifies a value while updating the tree structure, and sumRange calculates the range sum over the tree.