| Idea: |
- addition is invertible: the sum of any interval \(\langle A,B \rangle\) is the difference of two prefix sums, \(\mathrm{sum}\langle 1,B \rangle - \mathrm{sum}\langle 1,A-1 \rangle\) — so it suffices to maintain prefix sums
- transform the original array into an array of partial sums:
- every odd position keeps its original value
- every even position stores at least the sum of the current and the previous value
- every position divisible by 4 stores the sum of the last 4 values, every position divisible by 8 the sum of the last 8 values, …
- in general, position \(i\) stores the sum of the last \(\mathrm{lowbit}(i)\) values, where \(\mathrm{lowbit}(i)\) is the largest power of two dividing \(i\)
- to compute the prefix sum of, say, the first 43 values, write the number in binary to decompose it into powers of 2 (\(43 = 101011_2 = 32+8+2+1\)): the sum of values 1..32 is stored at position 32, the sum of the next 8 at position 40, the sum of the next 2 at position 42, and the last value at position 43
- in general, to compute the sum of interval \(\langle 1,i \rangle\), we add the value at position \(i\), remove the last 1-bit in the binary representation of \(i\), and repeat until \(i = 0\) — one addition per one-bit, \(O(\log n)\) in total
- after changing a value, all partial sums covering it must be fixed: these are found by repeatedly adding the lowest one-bit, again \(O(\log n)\) steps
- the partial sums form a tree — the parent of node \(i\) is \(i + \mathrm{lowbit}(i)\) — which is what this visualization draws; NOTE: the binary tree is implicit, the actual representation stored in memory consists of the tree array only
|