Implement a Fenwick Tree (Binary Indexed Tree) in JavaScript

This challenge asks you to implement a Fenwick Tree, also known as a Binary Indexed Tree (BIT). A Fenwick Tree is a data structure that efficiently supports two operations: updating an element in an array and querying the prefix sum of the array. This makes it incredibly useful for problems involving dynamic range queries and updates.

Problem Description

You need to create a JavaScript class called FenwickTree that represents a Fenwick Tree. The FenwickTree class should be initialized with an array of numbers. It should then provide methods to perform two core operations:

1. update(index, delta): This method should add delta to the element at index in the original array and propagate this change throughout the Fenwick Tree. The index is 0-based.
2. query(index): This method should return the prefix sum of the array from index 0 up to and including index. The index is 0-based.

Key Requirements:

• The Fenwick Tree should be initialized with a given array. The internal representation of the tree should be built based on this initial array.
• The update operation should modify the tree such that subsequent query operations reflect the change.
• The query operation should efficiently return the sum of elements up to a given index.

Expected Behavior:

• Initialization should correctly build the Fenwick Tree from the input array.
• update operations should be efficient, typically O(log n).
• query operations should be efficient, typically O(log n).

Edge Cases to Consider:

• Empty input array during initialization.
• Updating an index at the boundaries (0 and n-1).
• Querying at the boundaries (0 and n-1).
• Adding a delta of 0 to an element.
• Handling negative numbers in the input array and during updates.

Examples

Example 1:

Input:
initialArray = [1, 2, 3, 4, 5]

// Create FenwickTree
const ft = new FenwickTree(initialArray);

// Query prefix sum up to index 2 (elements at index 0, 1, 2)
const sum1 = ft.query(2); // Should be 1 + 2 + 3 = 6

// Update element at index 1 by adding 10
ft.update(1, 10); // Array conceptually becomes [1, 12, 3, 4, 5]

// Query prefix sum up to index 2 again
const sum2 = ft.query(2); // Should be 1 + 12 + 3 = 16

// Query prefix sum up to index 4 (entire array)
const sum3 = ft.query(4); // Should be 1 + 12 + 3 + 4 + 5 = 25

Output: sum1: 6 sum2: 16 sum3: 25

Explanation: Initially, the tree is built from [1, 2, 3, 4, 5]. query(2) sums the first 3 elements. After updating index 1 by adding 10, the conceptual array becomes [1, 12, 3, 4, 5]. query(2) now sums the first 3 elements of the updated array. query(4) sums all elements.

Example 2:

Input:
initialArray = []

// Create FenwickTree with an empty array
const ft = new FenwickTree(initialArray);

// Querying an empty tree should ideally return 0 or handle gracefully
const sum1 = ft.query(0); // Should be 0

// Update an element (this might be an invalid operation if tree is empty or index out of bounds)
// For this challenge, assume valid index operations after initialization for non-empty arrays.
// If you need to support adding elements dynamically, that's a more advanced variation.

Output: sum1: 0

Explanation: An empty Fenwick Tree should return 0 for any prefix sum query.

Constraints

• The input initialArray will contain integers.
• The size of initialArray (n) will be between 0 and 10^5.
• The values in initialArray and the delta in update will be within the range of -1000 to 1000.
• index for update and query will be 0-based and within the valid range of the initialized array.
• The implementation should aim for O(log n) time complexity for both update and query operations.

Notes

• A Fenwick Tree typically uses 1-based indexing internally for its bit manipulation logic, even though the public API (your class methods) will use 0-based indexing. You'll need to handle this conversion.
• The core idea behind Fenwick Trees involves leveraging the binary representation of indices to efficiently aggregate sums. The i & -i operation is crucial for navigating the tree structure.
• Consider how to initialize the Fenwick Tree. A naive approach of calling update for each element of the initial array is O(n log n). There are O(n) initialization methods as well, but O(n log n) is acceptable for this challenge.
• Think about the size of your internal tree array. It should be n + 1 if you're using 1-based indexing internally, where n is the size of the original array.