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.
• 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!