A lesson on binary indexed trees (Fenwick trees).

Implementing Binary Indexed Trees in Python

Good job on getting this far in the lesson on binary indexed trees! A binary indexed tree is a powerful data structure and great to add to your skillset. Let’s recap everything that we have done so far.

* A binary indexed tree is a data structure we can use to efficiently calculate prefix sums or range sum queries.
* The binary indexed tree is represented as an array.
* Binary index trees use 1-based indexing.
* A binary index tree offers *O(logn)* look-up time and *O(logn)* update time.
* The values in an element of a binary indexed tree are computed based on the range of responsibility.
* The formula for range of responsibility is:
 * range = 2r where *r* represents the right-most one bit in the binary representation of an index.
* The value at index *i* in a binary indexed tree is the sum of all elements in the range of responsibility of *i*, including *i*.
* To compute a prefix sum up to index *i* using a binary indexed tree, you find the range of responsibility of index *i*, then find the index that is at *i - range_of_responsibility(i)* and repeat this process by cascading down until you arrive at 0. The prefix sum is the sum of all elements you encounter.
* A range sum between *i* and *j* inclusive is computed by finding `prefix_sum(j) - prefix_sum(i-1).
* Updating a value in a binary indexed tree takes O(logn) time.
* To update a value, you add the difference between the new value and the old value at index *i* to all the elements in which *i* is in their range of responsibility.
* A binary indexed tree is constructed in O(n) time using point updates.

Happy Coding!

Review

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:

```py
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:
```python
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:
```python
nxt = i + (i&-i)
```
3. Add the value at index `i` to the value at index `next`:
```python
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:

```py
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.

Constructing a Binary Indexed Tree

We will now look at computing a range sum query, one of the main applications of using a binary indexed tree.

First, we have to calculate a prefix sum to calculate a range sum. Calculating a prefix sum up to index *i* is done as follows:

1. Compute the range of responsibility of index *i*.
2. Add the element at index *i* in the binary indexed tree to a running sum.
3. Go to the next index, which is at *i - range_of_responsibility(i)*. 
4. Repeat this process by going up the tree until you reach 0. 

Consider the following array and its associated binary indexed tree:

```py
arr = [2, -9, 6, 7, -1, 4, 1, 10, -12, 13, 27, -2, 4]
```
```py
binary_indexed_tree = [2, -7, 6, 6, -1, 3, 1, 20, -12, 1, 27, 26, 4]
```

For example, let’s say we want to compute the prefix sum up to index 7 (1-based indexing), we do the following:
1. `prefix_sum = binary_indexed_tree[7]`, `range_of_responsibility(7) = 1`
2. Next index: 7 - 1 = 6
3. `prefix_sum += binary_indexed_tree[6]`, `range_of_responsibility(6) = 2`
4. Next index: 6 - 2 = 4
5. `prefix_sum += binary_indexed_tree[4]`, `range_of_responsibility(4) = 4`
6. Next index: 4 - 4 = 0, done!

So the prefix sum is binary_indexed_tree[7] + binary_indexed_tree[6] + binary_indexed_tree[4] = 1 + 3 + 6 = 10

The following picture illustrates this algorithm. The path in red outlines the computations above.

![binary indexed tree](https://static-assets.codecademy.com/Courses/adv-algorithms-data-structures/BIT_E3.jpg)

When executing the algorithm, to find the next index to go to, it is not necessary to compute the range of responsibility and subtract it from the current index. To find the next index, you switch the right-most one bit in the binary representation of the current index (index *i*) from 1 to 0 and go to the resulting index (*i* now becomes the new index). This can be done using the following bit manipulation operation: `i -= i&-i`. The prefix sum is calculated by looping until *i* == 0.

Here is the code for the prefix sum algorithm:

```py
arr = [2, -9, 6, 7, -1, 4, 1, 10, -12, 13, 27, -2, 4]
binary_indexed_tree = [2, -7, 6, 6, -1, 3, 1, 20, -12, 1, 27, 26, 4]

prefix_sum = 0

# Compute prefix sum up to index 7 in arr (1-based indexing)

i = 7
while i > 0:
  # i-1 because in Python arrays are 0-based indexing. Element 7 is at index 6.
  prefix_sum += binary_indexed_tree[i-1]
  i -= i&-i
```
We can now use the prefix sums to compute the range query from [i, j]: 

> `range = prefix_sum(j) - prefix_sum(i-1)`

Computing Range Sum Using a Binary Indexed Tree

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

```py
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[6] + arr[5] = 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[10] + arr[9] = 4 + 2 = 6* 

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

```py
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.

Range of Responsibility

To the right, we have an example we outlined in the previous article. We described prefix sums and how we can utilize binary indexed trees as an efficient way to compute them. Recall that each element in a binary indexed tree has a range of responsibility that we can use to compute the value of the element. Using Python, in this lesson, you will practice:
* Constructing a binary indexed tree
* Computing the range of responsibility of an element
* Updating a binary indexed tree
* Computing a prefix sum using a binary indexed tree

Introduction

To update an element at index *i* in an array, we:
* Take the difference between the new element and the old element
* Add this difference to all the elements in which index *i* is in their range of responsibility within the tree.

To find the immediate next index in which *i* is in its range of responsibility, we add the right-most one bit of *i* to *i*and update *i*. We do this like so:

```python
i = i + (i & -i)
```

We update *i* because we need to do this for all indices that contain the original index in their range of responsibility. We repeat this step until *i* exceeds the size of the binary indexed tree. And remember, we add the difference between the new value and the old value, not the new value itself, because the original value itself already contributed to the computation of the original binary indexed tree.

Let’s look at an example. Consider the following array and its corresponding binary indexed tree:

```py
arr = [5, -12, 4, 11, 8, -9, 2, -3, -4, 7]

binary_indexed_tree = [5, -7, 4, 8, 8, -1, 2, 6, -4, 3]
```

Let’s say we want to update the element at index 3 (*i* = 3) in the array from 4 to 9. Here is the algorithm (remember, this is all 1-based indexing):

1. Compute the difference: 9 - 4 = 5
2. Add 5 to element at index 3: `binary_indexed_tree[3] = 9`
3. Find the immediate next index: i = i + (i & -i) = 3 + 3&-3 = 4
4. Add 5 to element at index 4: `binary_indexed_tree[4] = 13`
5. Find the immediate next index: i = i + (i & -i) = 4 + 4&-4 = 8
6. Add 5 to element at index 8: `binary_indexed_tree[8] = 2
7. Find the immediate next index: i = i + (i & -i) = 8 + 8&-8 = 16
8. 16 exceeds the size of the binary indexed tree (the size is 10) so we’re done!

The new binary indexed tree now becomes:

```py
binary_indexed_tree = [5, -7, 9, 13, 8, -1, 2, 11, -4, 3]
```

Here it is in code:

```py
arr = [5, -12, 4, 11, 8, -9, 2, -3, -4, 7]
binary_indexed_tree = [5, -7, 4, 8, 8, -1, 2, 6, -4, 3]

# Update element 3 from 4 to 9 (remember, this is 1-based indexing)
arr = [5, -12, 9, 11, 8, -9, 2, -3, -4, 7]

# Update algorithm
i = 3
diff = 9 - arr[i - 1] # i-1 because arrays are 0-based indexing in Python
while i <= len(binary_indexed_tree):
 binary_indexed_tree[i - 1] += diff
 i = i + (i & -i) 

print(binary_indexed_tree) # Output will be [5, -7, 9, 13, 8, -1, 2, 11, -4, 3] 
```

The update algorithm runs in *O(logn)* time.