Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Solution Explanation

This problem requires designing a data structure that supports efficient range sum queries and updates. Two common approaches are using a Binary Indexed Tree (BIT) or a Segment Tree. Both solutions are presented below.

Approach 1: Binary Indexed Tree (BIT)

A Binary Indexed Tree, also known as a Fenwick Tree, is a data structure that allows for efficient prefix sum queries and updates in O(log n) time. It achieves this by cleverly representing the prefix sums in an array.

Core Idea: Each element in the BIT array c stores the sum of a range of elements in the original array nums. The range covered by c[i] depends on the binary representation of i. Specifically, c[i] represents the sum of elements from i - (i & -i) + 1 to i. The expression i & -i isolates the least significant bit of i.

Update Operation: To update an element nums[index] to val, we calculate the difference between the new value and the old value (delta = val - nums[index]). Then, we traverse the BIT array, adding delta to all relevant elements.

Query Operation: To calculate the sum of elements from index left to right, we compute the prefix sum up to right + 1 and subtract the prefix sum up to left.

Time Complexity:

• Update: O(log n) - logarithmic time due to the traversal of the BIT array.
• Query: O(log n) - logarithmic time for computing prefix sums.

Space Complexity: O(n) - linear space to store the BIT array.

Approach 2: Segment Tree

A Segment Tree is a tree-based data structure where each node represents a range of elements in the original array. The tree is built recursively, with each internal node covering a range that is the union of its children's ranges.

Core Idea: The root node covers the entire array. Internal nodes are recursively divided to cover sub-ranges. Leaf nodes represent single elements. Each node stores the sum of the elements in its range.

Update Operation: To update an element, we traverse the tree from the root to the leaf node corresponding to the index. We update the value of the leaf node and then propagate the change upwards, updating the sums in the parent nodes.

Query Operation: To find the sum of elements in a range, we traverse the tree. If a node's range completely falls within the query range, we add its sum to the result. Otherwise, we recursively explore the left and right subtrees.

Time Complexity:

• Update: O(log n) - logarithmic time due to the tree traversal.
• Query: O(log n) - logarithmic time for traversing the tree.

Space Complexity: O(4n) ≈ O(n) - linear space to store the segment tree (although it's 4 times the size of the input array in the worst case due to the way the tree is constructed).

Both approaches offer similar time and space complexities. The choice between them often depends on personal preference or other factors like the specific problem constraints. The Binary Indexed Tree (BIT) generally uses less memory. The Segment Tree's structure can be more easily extended to support other operations (e.g., range minimum/maximum queries). The provided code implements both methods for the given problem.