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 <stdlib.h>
2
3typedef struct {
4 int* nums;
5 int size;
6} NumArray;
7
8NumArray* numArrayCreate(int* nums, int numsSize) {
9 NumArray* numArray = (NumArray*) malloc(sizeof(NumArray));
10 numArray->nums = (int*) malloc(numsSize * sizeof(int));
11 numArray->size = numsSize;
12 for (int i = 0; i < numsSize; i++) {
13 numArray->nums[i] = nums[i];
14 }
15 return numArray;
16}
17
18void numArrayUpdate(NumArray* obj, int index, int val) {
19 obj->nums[index] = val;
20}
21
22int numArraySumRange(NumArray* obj, int left, int right) {
23 int sum = 0;
24 for (int i = left; i <= right; i++) {
25 sum += obj->nums[i];
26 }
27 return sum;
28}
29
30void numArrayFree(NumArray* obj) {
31 free(obj->nums);
32 free(obj);
33}In this C solution, an array is allocated to store the elements. The update operation directly modifies a specific element, while the range sum is computed 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.