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 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}This Java solution creates an array to hold the numbers. The update method changes a specific index to the new value, and sumRange iterates over the selected range to compute the sum.
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.