Build your intuition. Fill in the missing part by typing it in.

Fenwick trees, also known as Binary Indexed Trees (BIT), are a data structure that efficiently supports range sum queries and updates in an array of numbers.

Fenwick trees are particularly useful when dealing with problems that involve updating array elements frequently and performing range sum queries.

The main idea behind Fenwick trees is to use the binary representation of the array indexes to store partial sums. Each index of the Fenwick tree corresponds to a range of indexes in the original array.

To update an element at index i in the original array, you would update all the corresponding Fenwick tree indexes that include i.

To get the prefix sum of elements up to index i in the original array, you would sum all the corresponding Fenwick tree indexes up to i.

To get the range sum of elements between index start and end in the original array, you would subtract the prefix sum at index start-1 from the prefix sum at index end.

The time complexity of updating an element and getting the prefix sum or range sum in a Fenwick tree is O(log n), where n is the size of the array.

A Fenwick tree can be implemented using an array of integers.

Here's an incomplete implementation of the update method for a Fenwick tree:

1void update(int index, int value) {
2  while (index <= n) {
3    // TODO: Update index in the Fenwick tree
4    index += index & (-index);
5  }
6}