Return to Answer

Given this tree structure, it's easy to determine the cumulative sum up to a point. The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question. As we do so, we also the following: any time that we move right, we also add in the current value to the counter.

Given this tree structure, it's easy to determine the cumulative sum up to a point. The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question. As we do so, we also do the following: any time that we move right, add the current value to the counter.

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links. For example, during a lookup, we just care about the left links we follow. During an update, we just care about the right links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links. For example, during a lookup, we just care about the right links we follow. During an update, we just care about the left links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

• Write out node n in binary.
• Set the counter to 0.
• Repeat the following while n ≠ 0:
  • Add in the value at node n.
  • Remove the rightmost 1 bit from n.

• Write out node n in binary.
• Set the counter to 0.
• Repeat the following while n ≠ 0:
  • Add in the value at node n.
  • Clear the rightmost 1 bit from n.