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.
Calculate the range of responsibility of index 12 and assign your answer to the variable
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).
Calculate the range of responsibility of index 15 and assign your answer to the variable