Implement a Segment Tree for Range Sum Queries in JavaScript

This challenge requires you to implement a Segment Tree data structure in JavaScript capable of efficiently handling range sum queries on an array of numbers. Segment trees are powerful for problems involving frequent updates and range queries on static or dynamic arrays, and mastering them is a key step in competitive programming and algorithm design.

Problem Description

You need to create a SegmentTree class in JavaScript that can perform two primary operations:

1. Build: Initialize the segment tree from a given array of numbers.
2. Query: Calculate the sum of elements within a specified range (inclusive) of the original array.

The segment tree should be built to support range sum queries. This means that each node in the tree will store the sum of the elements in the corresponding segment of the original array.

Key Requirements:

• The SegmentTree class should have a constructor that accepts an array of numbers.
• The constructor should build the segment tree.
• The class should have a query(left, right) method that returns the sum of elements in the original array from index left to right (inclusive).
• The implementation should be efficient. Building the tree should ideally be O(n), and each query should be O(log n), where n is the size of the input array.

Expected Behavior:

• When the SegmentTree is initialized with an array, it should correctly store and represent the sums of its segments.
• Calling query(left, right) should return the exact sum of elements from arr[left] to arr[right].

Edge Cases:

• Empty input array.
• Queries where left equals right.
• Queries covering the entire array.
• Queries with left > right (assume this is invalid input and can be handled by returning 0 or throwing an error, but for this challenge, let's assume left <= right).

Examples

Example 1:

Input:
const arr = [1, 3, 5, 7, 9, 11];
const segmentTree = new SegmentTree(arr);

Query 1: left = 1, right = 4
Output: 24
Explanation: The sum of elements from index 1 to 4 (inclusive) is 3 + 5 + 7 + 9 = 24.

Query 2: left = 0, right = 5
Output: 36
Explanation: The sum of elements from index 0 to 5 (inclusive) is 1 + 3 + 5 + 7 + 9 + 11 = 36.

Example 2:

Input:
const arr = [2, 4, 6];
const segmentTree = new SegmentTree(arr);

Query 1: left = 0, right = 0
Output: 2
Explanation: The sum of the element at index 0 is 2.

Query 2: left = 1, right = 2
Output: 10
Explanation: The sum of elements from index 1 to 2 is 4 + 6 = 10.

Example 3: Empty Array

Input:
const arr = [];
const segmentTree = new SegmentTree(arr);

Query 1: left = 0, right = 0
Output: 0
Explanation: An empty array has no elements, so any range sum should be 0.

Constraints

• The input array will contain non-negative integers.
• The size of the input array (n) will be between 0 and 10⁵.
• Query range indices (left, right) will be valid indices within the original array's bounds, and 0 <= left <= right < n. If the array is empty, left and right might be 0.
• The values in the array will not exceed 1000.
• Your solution should aim for a time complexity of O(n) for building the tree and O(log n) for each query.

Notes

• A segment tree is typically implemented using an array. The size of this array is usually around 4 * n to accommodate all nodes.
• You will need a helper function for the recursive building process and another for the recursive query process.
• Consider how to map array indices to segment tree nodes and vice-versa.
• Think about the base cases for your recursive functions.