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.
As an optional challenge, construct the binary index tree of