Learn

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 = 2
^{r}where*r*represents the right-most one bit in the binary representation of an index.

- range = 2
- 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!

### Instructions

As an optional challenge, construct the binary index tree of `arr`

.

# Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.