Fenwick trees

Problem

Prefix sums are perfect until the array changes, and then one update rewrites every prefix after it. A segment tree fixes that, but it needs 2n to 4n slots and 30 or more lines. When the question is only ever "sum of the first i values" or "sum of a range" with point updates, or anything else built from an operation that can be undone, a Fenwick tree does the same job in n + 1 slots and about ten lines.

Intuition

Every positive whole number is a sum of distinct powers of two, the ones its binary form has set. Seven is 4 + 2 + 1. So the first seven values of an array split into a block of 4, then a block of 2, then a block of 1: positions 1 to 4, 5 to 6, and 7. If every block of that kind were already summed and stored, any prefix would cost one addition per set bit.

A Fenwick tree stores exactly those blocks. Slot i holds the block that ends at position i and whose length is i's lowest set bit: slot 6 (110 in binary) holds positions 5 to 6, slot 4 (100) holds 1 to 4, slot 7 (111) holds just 7. Reading a prefix means starting at slot i and repeatedly dropping the lowest set bit to jump to the block just before. Updating position i means fixing every block that covers it, which you reach by repeatedly adding the lowest set bit.

Bars sit on rows by block length: length 8 on top, then 4, 2 and 1. The green bars are the slots a prefix of 7 reads, and they tile positions 1 to 7 with no gap or overlap. The diagram scrolls sideways on a narrow screen.

Mechanics

The lowest set bit

i & -i keeps only the lowest set bit of i: in two's complement, -i flips every bit above it and keeps it, so the AND leaves that one bit (the trick from bit manipulation). Write lowbit(i) for it. Indices start at 1, because 0 has no set bit and would loop forever.

The invariant

Slot i holds the sum of positions i − lowbit(i) + 1 through i. Everything else follows from that one sentence.

• Prefix. Slot i covers the top lowbit(i) positions of [1, i]. What remains is [1, i − lowbit(i)], so jump to i − lowbit(i) and repeat until 0. Each jump clears one set bit, so there are at most as many steps as i has set bits, at most ⌊log₂ n⌋ + 1.
• Update. The slots whose block contains position i are i itself, then i + lowbit(i), then that plus its lowbit, and so on. Adding the lowbit carries into a strictly higher bit, so the lowbit at least doubles each step and there are at most log₂ n + 1 steps. Each of those blocks starts at or before i, and no slot skipped over can contain i: any j between two consecutive stops has a lowbit too small to reach back to i.
• Range. The sum of [left, right] is prefix(right) − prefix(left − 1). This needs subtraction, which is why the plain tree handles sums, counts and XOR but not min or max.

Worked example

The slots over [5, 8, 6, 3, 2, 7, 2, 6].

Prefix sum of the first 7. Strip the lowest set bit each step:

The prefix of 2 is 13, read from 1 slot, so the sum of positions 3 to 7 is 33 − 13 = 20.

Add 7 at position 3. Add the lowest set bit each step:

3 of 8 slots change, and the array is now [5, 8, 13, 3, 2, 7, 2, 6].

The amber bars are the slots an update at position 3 changes: every bar that sits over position 3, and no other.

Counting smaller values to the right of each element in [3, 1, 4, 1, 5, 9, 2, 6]. Ranks compress the values to 1→1, 2→2, 3→3, 4→4, 5→5, 6→6, 9→7. Walking from the right, each element asks for the prefix sum up to its rank minus 1, then adds 1 at its rank:

The counts in original order are [3, 0, 2, 0, 1, 2, 0, 0].

Implementation

class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def prefix(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def range_sum(self, left, right):
        return self.prefix(right) - self.prefix(left - 1)

Positions are 1-based. To start from an existing array, call add(i, nums[i - 1]) for every i, which costs O(n log n), or use the linear build below. To set a position to a new value rather than add to it, add new − old and keep the array alongside the tree.

Variations and edge cases

Linear build. Each slot pushes its finished total into the one slot directly above it, its parent i + lowbit(i). Going left to right, a slot is complete before it is pushed:

def build(nums):
    tree = [0] + list(nums)
    for i in range(1, len(tree)):
        parent = i + (i & -i)
        if parent < len(tree):
            tree[parent] += tree[i]
    return tree

Range add, point query. Store the differences instead of the values. Adding v to [l, r] is add(l, v) and add(r + 1, -v) (skip the second when r is the last position), and the current value at i is prefix(i), the same move as a difference array in prefix sums.

Counting smaller values. The worked example's loop:

def count_smaller(nums):
    ranks = {value: rank for rank, value in enumerate(sorted(set(nums)), 1)}
    seen = Fenwick(len(ranks))
    counts = [0] * len(nums)
    for index in range(len(nums) - 1, -1, -1):
        rank = ranks[nums[index]]
        counts[index] = seen.prefix(rank - 1)
        seen.add(rank, 1)
    return counts

Walk from the left and ask index − seen.prefix(rank) for "how many earlier values are larger", which counts inversions.

Find the k-th smallest. When the tree stores counts (all non-negative), descend by powers of two: try each block from the largest down and step over it whenever its count is still below k. It returns the smallest position whose prefix reaches k in O(log n), without a binary search over prefix:

def find_kth(tree, k):
    pos, step = 0, 1 << (len(tree) - 1).bit_length()
    while step:
        if pos + step < len(tree) and tree[pos + step] < k:
            pos += step
            k -= tree[pos]
        step //= 2
    return pos + 1

• Index 0. add(0, v) loops forever, since 0 & -0 is 0. Shift 0-based positions by one on the way in.
• Ranks must start at 1 for the same reason, and prefix(rank − 1) then cleanly returns 0 for the smallest value.
• Equal values. "Strictly smaller" asks prefix(rank − 1); "smaller or equal" asks prefix(rank). Duplicates share one rank.
• Negative values in the array are fine for sums, but find_kth needs non-negative counts, because the descent assumes prefixes only grow.

Complexity and tradeoffs

add and prefix are O(log n), building is O(n) or O(n log n), and the tree uses n + 1 slots. The bounds, checked by trying every position:

• Brute-force baseline. A plain array updates in O(1) but sums a range in O(n), so q queries cost O(qn). Prefix sums flip that: O(1) queries, O(n) updates. The tree makes both O(log n).
• Against a segment tree. Same O(log n), a quarter of the memory, a fraction of the code and smaller constants. But it only answers ranges through subtraction, so range min and max, and range updates with range queries, need the segment tree (or two Fenwick trees for the sum case).
• Against prefix sums. With no updates, plain prefix sums answer in O(1). The tree is for when updates and queries interleave.
• Against merge sort. Counting inversions or smaller-after-self also falls out of merge sort in O(n log n), with no tree and no rank compression. The Fenwick version wins when the values arrive one at a time.
• In an interview. It is short enough to write from memory, which makes it the practical choice whenever a sum-only problem needs updates.

Problems

No problem on the four lists has this page as its home, which is why it sits under Beyond the interview.

For practice beyond the lists, in rising difficulty:

• 307. Range Sum Query - Mutable Medium
  The template exactly: keep the values beside the tree so a set becomes an add of the difference.
• 315. Count of Smaller Numbers After Self Hard
  The worked example: ranks, a right-to-left walk, and one prefix query per element.
• 493. Reverse Pairs Hard
  Rank both each value and twice each value, then count earlier values above twice the current one.
• 1649. Create Sorted Array through Instructions Hard
  Each insertion costs the smaller of "strictly less" and "strictly greater" counts so far, two prefix queries over values.

Connections

A Fenwick tree is prefix sums with the work spread across the binary digits of the index, and its two loops are the lowest-set-bit trick from bit manipulation. It does a subset of what a segment tree does, more cheaply. Counting smaller values over ranks solves the same problems as a merge-sort count or a BST with subtree sizes, and a max-version over ranks speeds up LIS-style DPs, since "best answer among smaller values" is a prefix max that only ever grows.

Check yourself

References

• Fenwick, P. M., "A new data structure for cumulative frequency tables", Software: Practice and Experience 24(3):327–336, 1994: the original paper.
• Ryabko, B. Ya., "A fast on-line adaptive code", IEEE Transactions on Information Theory 38(4):1400–1404, 1992: an earlier description of the same structure.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, problem 2-4 (inversions) and chapter 14, "Augmenting Data Structures", for order statistics the same tree answers.
• Sedgewick and Wayne, Algorithms, 4th edition, section 2.2, for counting inversions with merge sort, the static alternative.
• Skiena, S., The Algorithm Design Manual, the catalog entry "Range Search", on choosing among range-query structures.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.