Implement the data structure itself, from scratch. A FenwickTree holds size numbers, all 0 to begin with.
new FenwickTree(size) — size zerosupdate(i, delta) — adds delta to the value at the 0-based index i (this one is a delta, not a replacement)prefixSum(i) — the sum of indices 0 through i inclusive; prefixSum(-1) is 0- Both operations must be O(log size)
- Deltas may be negative
The trick the structure is built on: index x of the internal array covers the x & -x values ending at x, where x & -x isolates the lowest set bit.