Fenwick Tree (BIT), in depth: deriving lowbit, linear-time build, binary-lifting search, inversion counting and the bugs that bite

The lowbit trick from twos complement

Everything rests on one quantity: lowbit(i), the value of the lowest set bit of i. For 6, binary 110, it is 2; for 8, binary 1000, it is 8; for any odd number it is 1. In code it is i & -i, and the reason is twos complement. Negating a number flips every bit and adds one. Flipping turns the trailing zeros of i into ones and its lowest one into a zero; adding one carries through those ones and stops exactly at that position, setting it back to one. Above that position every bit of -i is the complement of the corresponding bit of i, so the AND keeps only the lowest set bit. For 12, binary 01100, the negation is 10100 in five bits and the AND is 00100, which is 4.

Python integers are unbounded, but the identity still holds because Python defines bitwise operators on negative numbers as if they had infinitely many leading ones. For more on the underlying idioms see bit manipulation fundamentals.

Responsibility ranges and the two walks

Cell t[i] stores the sum of the lowbit(i) elements ending at i: the half-open range (i - lowbit(i), i]. Odd cells hold one element, cells at multiples of 2 but not 4 hold two, and so on, with the cell at the largest power of two holding a whole prefix.

A prefix query for prefix(i) adds t[i], which covers the last lowbit(i) elements, then continues at i - lowbit(i), which is i with its lowest set bit cleared. Each step removes one set bit, so the loop runs exactly popcount(i) times, at most floor(log2 n) + 1.

An update at position i must change every cell whose range contains i. Those are i, then i + lowbit(i), and so on. Adding the lowest set bit clears it and carries into a higher position, so the lowbit of the next index is at least double the current one. It can double at most about log2 n times before the index exceeds n, which gives the same bound. The proof that these are exactly the covering cells is short: a cell j covers i when j - lowbit(j) < i <= j, and the carry chain enumerates precisely the indices that satisfy that while skipping none.

Implementation

class Fenwick:
    """Prefix sums over positions 1..n with point updates."""

    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)          # t[0] is unused

    def add(self, i, delta):            # a[i] += delta
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def prefix(self, i):                # a[1] + ... + a[i]
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s

    def range_sum(self, lo, hi):        # a[lo] + ... + a[hi]
        return self.prefix(hi) - self.prefix(lo - 1)

Range sums use subtraction, which is why the structure needs an invertible operation. There is no set operation: to assign a value, keep a plain copy of the array and call add(i, new - a[i]). Point reads also come from that copy, or from range_sum(i, i) at logarithmic cost.

Worked example

Take a = [5, 2, 0, 7, 3, 1, 4, 6] at positions 1 to 8. The tree array is t = [5, 7, 0, 14, 3, 4, 4, 28].

The query range_sum(3, 6) is prefix(6) - prefix(2). The first walks 6 then 4 and adds 4 + 14 = 18; the second reads t[2] = 7. The answer is 11, which matches 0 + 7 + 3 + 1. Now add(3, 4): the walk visits 3, then 3 + 1 = 4, then 4 + 4 = 8, and stops because 16 exceeds 8. The array becomes [5, 7, 4, 18, 3, 4, 4, 32], and only those three cells changed.

Building in linear time

Building by calling add n times costs O(n log n). A linear build exists because each cell has exactly one parent, the next cell up the update chain. Copy the values in, then sweep left to right and push each finished cell into its parent once.

    @classmethod
    def from_list(cls, values):
        f = cls(len(values))
        t = f.t
        for i, v in enumerate(values, start=1):
            t[i] += v                    # t[i] now holds its whole range
            parent = i + (i & -i)
            if parent <= f.n:
                t[parent] += t[i]
        return f

When the sweep reaches i, every child of i has a smaller index and has already pushed into it, so t[i] is complete before it is pushed on. For a few million elements the difference between the two builds is noticeable at start-up, and the linear version also avoids an accidental quadratic when someone rebuilds per request.

Searching by cumulative count

Often the question is inverted: find the smallest position whose prefix sum reaches a target. That is how you get the k-th smallest element of a multiset stored as counts, or pick a weighted random item. Binary searching over prefix costs O(log² n). The tree supports O(log n) directly by descending through powers of two.

    def lower_bound(self, target):
        """Smallest i with prefix(i) >= target, or n + 1 if none.
        Requires every a[i] >= 0, so prefix sums never decrease."""
        pos, rem = 0, target
        step = 1 << (self.n.bit_length() - 1) if self.n else 0
        while step:
            nxt = pos + step
            if nxt <= self.n and self.t[nxt] < rem:
                pos = nxt                # the whole block fits under the target
                rem -= self.t[nxt]
            step >>= 1
        return pos + 1

At each step pos is a multiple of twice the current step, so t[pos + step] covers exactly the next step elements after pos. If that block still leaves the running total short of the target, skip it; otherwise keep it for a finer step. On the example, lower_bound(15) tests t[8] = 28, too big; t[4] = 14, taken, leaving 1; t[6] = 4, too big; t[5] = 3, too big; answer 5, and indeed prefix(4) = 14 and prefix(5) = 17.

The non-negativity requirement is real. With negative values, prefix sums are not monotone, the smallest index reaching the target is not well defined by this descent, and the function returns a wrong answer without any error.

Counting inversions

An inversion is a pair of positions i < j with x[i] > x[j]. Counting them measures how far a list is from sorted and appears in ranking metrics such as Kendall tau. Scan left to right, keep a Fenwick tree of counts indexed by value rank, and for each element count how many earlier elements are strictly greater.

def count_inversions(xs):
    ranks = {v: r for r, v in enumerate(sorted(set(xs)), start=1)}
    f = Fenwick(len(ranks))
    inv = 0
    for seen, x in enumerate(xs):
        r = ranks[x]
        inv += seen - f.prefix(r)       # earlier elements with rank > r
        f.add(r, 1)
    return inv

Coordinate compression maps arbitrary values to ranks 1..m, so the tree is sized by distinct values rather than the value range. Equal values share a rank and are not counted, which is the usual definition. For [3, 1, 2, 3, 0] the function returns 6. The whole thing is O(n log n), the same as the merge-sort method, with less code.

What else the structure can hold

The requirement behind range queries is an invertible, associative operation: sums, xor, and products over a group where no element is zero. Prefix-only queries need less. A prefix maximum works if values only ever increase, because a cell can be raised but never lowered; arbitrary range maximum needs a segment tree.

Two standard extensions build on the same array. Range add with point query stores a difference array in the tree, and range add with range sum uses two trees; both are worked through in range updates in depth. The structure also generalises to a grid by nesting the loops, which is covered in 2D Fenwick trees.

Engineering details

Off-by-one is the most common bug. Index 0 must never enter the update loop, because 0 & -0 is 0 and the loop never terminates. Convert at the boundary: public methods take 0-based indices and add one, and nothing inside the class sees a 0-based index.

In fixed-width languages, size the cells for the largest prefix, not the largest element; a million 32-bit counts can overflow a 32-bit total. With floating point, repeated adds and subtracts accumulate rounding error that a recomputed sum would not, so rebuild periodically from the source array or use integers in fixed units.

Performance is good because the array is flat. Updates walk upward with growing strides and touch few cache lines near the top, which is hot anyway. For concurrent use, a single lock around operations is usually enough; if writes dominate, shard by key and combine shard prefix sums, or batch updates and apply them with the linear build.

Failure modes

• Infinite loop on index 0. A 0-based index passed straight into add hangs the process.
• Using range_sum for min or max. Subtraction does not invert max, so answers are silently wrong.
• Searching with negative values. lower_bound assumes monotone prefixes and returns a wrong index otherwise.
• Assign treated as add. Calling add(i, v) to set a value double counts the old value.
• Overflow and drift. Narrow integer cells overflow on large totals; floating point cells drift over millions of updates.
• Uncompressed coordinates. Sizing the tree by the maximum value instead of the number of distinct values wastes memory or fails outright.

Trade-offs

What to do next

1. Type the class above and test it against a brute-force sum on random arrays, including n = 0 and n = 1.
2. Add the linear build and assert it produces the same array as n calls to add.
3. Implement lower_bound and use it for k-th smallest on a multiset of counts.
4. Count inversions on a random permutation and compare with an O(n²) loop.
5. Wrap the class so callers use 0-based indices and cannot pass index 0 inside.
6. Read the range-update and 2D articles linked above, then decide whether your problem needs a segment tree instead.