Learn

In this exercise, you will practice computing a value in a binary indexed tree by using the range of responsibility. Consider the following array:

``arr = [1, 12, 3, 6, 8, 16, 10, 20, 2, 4]``

Recall the following formula for range of responsibility:

• Let r represent the right-most one bit in the binary representation of i.
• Range of responsibility = 2r elements below i including element i.

Remember, an array is considered 1-based (the first element is at index 1), in the context of binary indexed trees.

For example, let’s find the value of the element at index 6 in the binary indexed tree.

• In binary, 6 is 110b.
• The right-most one bit is at position 1, so the range of responsibility of index 6 is 21 = 2.
• Because of this, element 6 in the binary indexed tree will contain the sum of elements at indices 6 and 5 in the original array (remember to start counting at 1, not 0).
• The value at index 6 in the binary indexed tree is arr + arr = 16 + 8 = 24.

Let’s compute the value at index 10 in the binary indexed tree. In binary, 10 is 1010b. The right-most one bit is at position 1, so the range of responsibility is 21 = 2. The value at index 10 in the binary indexed tree is the sum of the value at index 10 and 9 in the original array, so arr + arr = 4 + 2 = 6

The full binary indexed tree associated with the previous array is:

``binary_indexed_tree =  [1, 13, 3, 22, 8, 24, 10, 76, 2, 6]``

In later exercises, we will see how to construct the binary indexed tree using the range of responsibility.

### Instructions

1.

Calculate the range of responsibility of index 12 and assign your answer to the variable `element12`.

Note: you may find the binary representation of the number in whatever manner you choose (either use Python, compute it manually using a calculator, or use Google).

2.

Calculate the range of responsibility of index 15 and assign your answer to the variable `element15`.