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 def __init__(self, nums):
3 self.nums = nums
4
5 def update(self, index, val):
6 self.nums[index] = val
7
8 def sumRange(self, left, right):
9 return sum(self.nums[left:right+1])In this Python solution, we define a list self.nums to store the numbers. The update method modified a specific index with a new value, while sumRange calculates the sum of numbers between indices left and right (inclusive) by using Python's built-in sum() function.
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__(self
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.