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.
1#include <vector>
2using namespace std;
3
4class NumArray {
5private:
6 vector<int> nums;
7public:
8 NumArray(vector<int>& nums) : nums(nums) {}
9
10 void update(int index, int val) {
11 nums[index] = val;
12 }
13
14 int sumRange(int left, int right) {
15 int sum = 0;
16 for (int i = left; i <= right; ++i) {
17 sum += nums[i];
18 }
19 return sum;
20 }
21};This C++ implementation uses a vector to manage the numbers, where update directly changes a specific element, and sumRange calculates the sum of values in the specified range using a simple loop.
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.