Implementing a Fenwick Tree (Binary Indexed Tree) in JavaScript

Fenwick Trees, also known as Binary Indexed Trees (BITs), are powerful data structures used for efficiently calculating prefix sums in an array and updating individual elements. They offer a significant performance advantage over naive approaches, especially when dealing with frequent updates and queries. This challenge asks you to implement a Fenwick Tree in JavaScript, enabling you to solve problems involving range queries and point updates.

Problem Description

You are tasked with creating a JavaScript class called FenwickTree that implements a Fenwick Tree. The class should support the following operations:

• constructor(size): Initializes the Fenwick Tree with a given size. The underlying array will be of size size + 1 (index 0 is unused).
• update(index, value): Updates the element at the given index by adding value to it. This operation should propagate the change through the tree to maintain correct prefix sum calculations. index is 1-based.
• query(index): Returns the prefix sum from index 1 up to the given index. index is 1-based.

The core idea behind a Fenwick Tree is to represent prefix sums in a tree-like structure where each node stores the sum of a specific range of elements from the original array. Efficient updates and queries are achieved by traversing this tree structure.

Examples

Example 1:

Input:
size = 5
updates: update(1, 3), update(2, -2), update(4, 5)
query: query(3)

Output: 1
Explanation:
Initial array (conceptually): [0, 0, 0, 0, 0]
After update(1, 3): [0, 3, 0, 0, 0]
After update(2, -2): [0, 3, -2, 0, 0]
After update(4, 5): [0, 3, -2, 5, 0]
query(3) returns the sum from index 1 to 3: 3 + (-2) = 1

Example 2:

Input:
size = 10
updates: update(2, 1), update(4, 2), update(6, 3)
query: query(7)

Output: 6
Explanation:
After updates, the prefix sum up to index 7 is 1 + 2 + 3 = 6

Example 3: (Edge Case)

Input:
size = 3
updates: update(1, 5)
query: query(0)

Output: 0
Explanation:
query(0) should always return 0 as it represents the sum of an empty prefix.

Constraints

• size will be an integer between 1 and 100,000 (inclusive).
• index for update and query will be an integer between 1 and size (inclusive).
• value for update will be an integer.
• The time complexity of update and query should be O(log n), where n is size.
• The space complexity should be O(n).

Notes

• Remember that Fenwick Trees use 1-based indexing.
• The update operation should add value to the element at the given index and propagate the change to all affected nodes in the tree.
• The query operation should efficiently calculate the prefix sum up to the given index by summing the values of relevant nodes in the tree.
• Consider how to efficiently determine the parent and next nodes during updates and queries. The least significant bit (LSB) is key to navigating the tree.
• Think about how to initialize the Fenwick Tree.