Fenwick tree

When the values change, prefix sums break: changing one value changes every prefix sum after it. A Fenwick tree stores a cleverly chosen set of partial sums, so that both a prefix sum and an update touch only about log₂ n of them. The whole structure is one list and two short loops.

Sums that change

Two operations, mixed in any order:

• add(i, v): add v to the value at position i;
• prefix(i): the total of the first i values. A range total is then prefix(r) − prefix(l), as in lesson 1.

A plain list makes add cost O(1) and prefix cost O(n). A list of prefix sums does the opposite. A Fenwick tree (Peter Fenwick, 1994; also called a binary indexed tree, BIT) makes both O(log n).

The lowest 1 bit

Count positions from 1, not 0: it makes the binary method work. Write a position i in binary, and look at its lowest 1 bit, the rightmost 1. Call its value low(i). For 6 = 110 it is 2; for 7 = 111 it is 1; for 8 = 1000 it is 8. In Python, i & -i gives it. (& keeps the bits that are 1 in both numbers, and in the way computers store -i, the only 1 bit it shares with i is the lowest one.)

So odd positions hold just their own value, t[6] holds positions 5 and 6, t[4] holds 1 to 4, and t[8] holds 1 to 8. The figure draws each t[i] as a bar that ends at position i, in a row for its length.

Prefix sum and update

Prefix sum. Start with i and add t[i]; it covers the last low(i) positions. The positions still missing are 1 to i − low(i), so continue from there. Taking away the lowest 1 bit each time, the loop runs once per 1 bit of i: at most log₂ n + 1 times. For 7 = 111: t[7] + t[6] + t[4].

Update. Changing position i must change every t[j] whose range covers i. The first is t[i] itself. The next is found by adding the lowest 1 bit: i + low(i). Each step makes the lowest 1 bit at least twice as large, so there are at most log₂ n + 1 steps. For 3: t[3], t[4], t[8].

The code

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)        # t[0] is not used

    def add(self, i, v):              # position i, counted from 1
        while i <= self.n:
            self.t[i] += v
            i += i & -i               # the next bar that covers i

    def prefix(self, i):              # total of positions 1..i
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i               # drop the lowest 1 bit
        return s

To use positions from 0, as Python lists do, call add(i + 1, v): the total of a[0:i] is then prefix(i). To build from a list of n values, calling add n times costs O(n log n). An O(n) build copies the values into t, then for each i from 1 up adds t[i] into t[i + low(i)] (if that is at most n).

Why it works

The prefix loop covers 1 to i exactly once. Each step covers positions i − low(i) + 1 to i, and then continues from i − low(i), so the pieces are next to each other with no gap and no overlap, down to 0.

The update loop finds every bar that covers i. A bar t[j] covers i when j ≥ i and j − low(j) < i. Start at j = i. Adding low(j) clears a run of 1 bits and sets the next 0 bit above them, so the new j agrees with the old one in all higher bits and has a larger low bit: its bar reaches back past the old one. Any j skipped over would have a low bit too small to reach back to i. So the loop visits exactly the bars that cover i, one per row of the figure.

A Fenwick tree needs an operation with an inverse (for range totals by subtraction), so it is used for sums, counts and XOR. It is smaller and faster than a segment tree, but less general.