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

Instructions

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

Take this course for free

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

Or sign up using:

Already have an account?