Bug 19: Prefix Sums That Don't Add Up
- This is a Fenwick tree. It represents n inclusive prefix sums.
- The Sum method returns the prefix sum at index i in logarithmic time.
- The Add method modifies the prefix sums at indexes i, i+1, ..., n-2, n-1 in logarithmic time.
- Element 0 of the underlying slice (tree) is a special case. The other slice elements are "fragments".
- Element i (for 1 <= i < n) is a partial sum ("fragment") of length k, where k is the lowest 1-bit of i.
- E.g., the fragment at index 4 is of length 4. At index 5, the length is 1. At index 6, the length is 2.
- The prefix sum at i is computed by adding fragments, clearing the lowest 1-bit of i until 0 is reached.
- When a fragment is modified, all the longer fragments that overlap it must also change.
Fix The Tiny Bug In This Go Code: