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:

- 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]
- Starting at index 1, find the next index in which 1 is in its range of responsibility:nxt = i + (i&-i)
- 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] - 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`

.