Learn

In this exercise, we will explore the technique of efficiently constructing a binary indexed tree in O(n) time using point updates.

To construct a binary indexed tree in linear time, we go through each element and perform exactly one point update; that is, for an index i, we only update the immediate next index in which i is in its range of responsibility by adding the value that is at i. We do this for every element in the binary indexed tree.

Let’s see an example. Consider the following array:

``arr = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3]``

The algorithm for constructing the associated binary indexed tree is:

1. Initialize the binary indexed tree as a copy of the original array:
``binary_indexed_tree = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3]``
2. Starting at index 1, find the next index in which 1 is in its range of responsibility:
``nxt = i + (i&-i)``
3. Add the value at index `i` to the value at index `next`:
``````nxt = 1 + (1 & -1) = 2
binary_indexed_tree[nxt] += binary_indexed_tree[i]``````
4. Do this for all remaining elements until `next` exceeds the size of the binary indexed tree.

Here it is in Python:

``````arr = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3]
binary_indexed_tree = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3]

for i in range(1, len(binary_indexed_tree) + 1):
nxt = i + (i & -i)
if nxt - 1 >= len(binary_indexed_tree):
continue
binary_indexed_tree[nxt - 1] += binary_indexed_tree[i - 1]

print(binary_indexed_tree) # Output will be [4, 11, -8, 12, 10, 23, -6, 31, 19, 8, -2, 3]``````

The lines `next - 1` and `i - 1` exist to correct for the offset from switching from 1-based indexing to 0-based indexing.

### Instructions

1.

Given `binary_indexed_tree`, compute a point update for the next index responsible for index 1 (index 1 is its range of responsibility).

2.

Find the binary indexed tree associated with `arr`; that is, update the `binary_indexed_tree` array to represent the binary indexed tree associated with `arr`.