Learn

To update an element at index i in an array, we:

  • Take the difference between the new element and the old element
  • Add this difference to all the elements in which index i is in their range of responsibility within the tree.

To find the immediate next index in which i is in its range of responsibility, we add the right-most one bit of i to iand update i. We do this like so:

i = i + (i & -i)

We update i because we need to do this for all indices that contain the original index in their range of responsibility. We repeat this step until i exceeds the size of the binary indexed tree. And remember, we add the difference between the new value and the old value, not the new value itself, because the original value itself already contributed to the computation of the original binary indexed tree.

Let’s look at an example. Consider the following array and its corresponding binary indexed tree:

arr = [5, -12, 4, 11, 8, -9, 2, -3, -4, 7] binary_indexed_tree = [5, -7, 4, 8, 8, -1, 2, 6, -4, 3]

Let’s say we want to update the element at index 3 (i = 3) in the array from 4 to 9. Here is the algorithm (remember, this is all 1-based indexing):

  1. Compute the difference: 9 - 4 = 5
  2. Add 5 to element at index 3: binary_indexed_tree[3] = 9
  3. Find the immediate next index: i = i + (i & -i) = 3 + 3&-3 = 4
  4. Add 5 to element at index 4: binary_indexed_tree[4] = 13
  5. Find the immediate next index: i = i + (i & -i) = 4 + 4&-4 = 8
  6. Add 5 to element at index 8: `binary_indexed_tree[8] = 2
  7. Find the immediate next index: i = i + (i & -i) = 8 + 8&-8 = 16
  8. 16 exceeds the size of the binary indexed tree (the size is 10) so we’re done!

The new binary indexed tree now becomes:

binary_indexed_tree = [5, -7, 9, 13, 8, -1, 2, 11, -4, 3]

Here it is in code:

arr = [5, -12, 4, 11, 8, -9, 2, -3, -4, 7] binary_indexed_tree = [5, -7, 4, 8, 8, -1, 2, 6, -4, 3] # Update element 3 from 4 to 9 (remember, this is 1-based indexing) arr = [5, -12, 9, 11, 8, -9, 2, -3, -4, 7] # Update algorithm i = 3 diff = 9 - arr[i - 1] # i-1 because arrays are 0-based indexing in Python while i <= len(binary_indexed_tree): binary_indexed_tree[i - 1] += diff i = i + (i & -i) print(binary_indexed_tree) # Output will be [5, -7, 9, 13, 8, -1, 2, 11, -4, 3]

The update algorithm runs in O(logn) time.

Instructions

1.

The array that generated binary_indexed_tree had element 1 update from 12 to 14. Update the Fenwick tree accordingly.

2.

In the original array, element 4 was updated from 7 to 3. Update the binary indexed tree accordingly.

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?