Learn

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:

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]

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

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:

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)

Instructions

1.

Given the array, arr, and its corresponding binary indexed tree, binary_indexed_tree, compute the prefix sum up to index i = 10. Remember, this is 1-based indexing.

Assign your answer to prefix_sum10.

Note this code should be very similar to the code in the narrative.

2.

Compute the range sum between index 10 and index 5. This is still 1-based indexing. Assign your answer to range_sum.

Sign up to start coding

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?