Learn

In this exercise, we will explore the technique of efficiently constructing a binary indexed tree in O(n) time using point updates.

To construct a binary indexed tree in linear time, we go through each element and perform exactly one point update; that is, for an index i, we only update the immediate next index in which i is in its range of responsibility by adding the value that is at i. We do this for every element in the binary indexed tree.

Let’s see an example. Consider the following array:

arr = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3]

The algorithm for constructing the associated binary indexed tree is:

  1. Initialize the binary indexed tree as a copy of the original array:
    binary_indexed_tree = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3]
  2. Starting at index 1, find the next index in which 1 is in its range of responsibility:
    nxt = i + (i&-i)
  3. Add the value at index i to the value at index next:
    nxt = 1 + (1 & -1) = 2 binary_indexed_tree[nxt] += binary_indexed_tree[i]
  4. Do this for all remaining elements until next exceeds the size of the binary indexed tree.

Here it is in Python:

arr = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3] binary_indexed_tree = [4, 7, -8, 9, 10, 13, -6, 2, 19, -11, -2, -3] for i in range(1, len(binary_indexed_tree) + 1): nxt = i + (i & -i) if nxt - 1 >= len(binary_indexed_tree): continue binary_indexed_tree[nxt - 1] += binary_indexed_tree[i - 1] print(binary_indexed_tree) # Output will be [4, 11, -8, 12, 10, 23, -6, 31, 19, 8, -2, 3]

The lines next - 1 and i - 1 exist to correct for the offset from switching from 1-based indexing to 0-based indexing.

Instructions

1.

Given binary_indexed_tree, compute a point update for the next index responsible for index 1 (index 1 is its range of responsibility).

2.

Find the binary indexed tree associated with arr; that is, update the binary_indexed_tree array to represent the binary indexed tree associated with 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?