Efficient Range Queries with a Segment Tree

Segment trees are powerful data structures used to efficiently answer range queries on an array. They allow for quick calculations (like sum, min, max, etc.) over specific segments of the array, and also support updates to individual elements. This challenge asks you to implement a segment tree in JavaScript to perform range sum queries.

Problem Description

You are tasked with implementing a segment tree that supports range sum queries. The segment tree should be built from an input array and then allow you to efficiently calculate the sum of elements within a given range. Your implementation should include the following functionalities:

1. build(arr): Constructs the segment tree from the input array arr. The tree should be represented as an array.
2. query(arr, left, right): Calculates the sum of elements in the array arr within the range [left, right] (inclusive).
3. update(arr, index, value): Updates the element at index in the original array arr to value and propagates the change through the segment tree.

The segment tree should be a complete binary tree represented as an array. The root of the tree is at index 0. The left child of node i is at index 2*i + 1, and the right child is at index 2*i + 2. Leaf nodes correspond to the elements of the original array.

Examples

Example 1:

Input: arr = [1, 3, 5, 7, 9, 11]
build(arr)  // Returns a segment tree array (implementation detail, not directly visible)
query(arr, 1, 3)
Output: 15
Explanation: The sum of elements from index 1 to 3 (inclusive) is 3 + 5 + 7 = 15.

query(arr, 0, 5)
Output: 36
Explanation: The sum of all elements is 1 + 3 + 5 + 7 + 9 + 11 = 36.

Example 2:

Input: arr = [2, 4, 6, 8, 10]
build(arr)
query(arr, 0, 2)
Output: 12
Explanation: The sum of elements from index 0 to 2 (inclusive) is 2 + 4 + 6 = 12.

update(arr, 2, 12)
query(arr, 0, 2)
Output: 18
Explanation: After updating arr[2] to 12, the sum from index 0 to 2 is 2 + 4 + 12 = 18.

Example 3: (Edge Case)

Input: arr = [5]
build(arr)
query(arr, 0, 0)
Output: 5
Explanation: Single element array, query on the single element returns the element itself.

update(arr, 0, 10)
query(arr, 0, 0)
Output: 10
Explanation: Updating the single element changes the value correctly.

Constraints

• The input array arr will contain non-negative integers.
• The length of the input array arr will be between 1 and 100,000 (inclusive).
• left and right in the query function will be valid indices within the bounds of the array (0 <= left <= right < arr.length).
• index in the update function will be a valid index within the bounds of the array (0 <= index < arr.length).
• The time complexity of build should be O(n), where n is the length of the array.
• The time complexity of query and update should be O(log n).

Notes

• The build function should return the segment tree array.
• Consider how to efficiently calculate the sum of a range during the query function using the precomputed sums stored in the segment tree.
• The update function needs to update the segment tree after modifying an element in the original array. Think about which nodes in the tree need to be updated.
• You can assume that the input array will not be modified directly outside of the update function.
• Focus on the core logic of the segment tree; you don't need to handle error cases like invalid input types.