Fenwick Trees (Binary Indexed Trees), Explained

A Fenwick tree, also called a binary indexed tree or BIT, is a data structure that answers prefix-sum queries and supports point updates on an array, both in O(log n) time. It solves the same core problem as a segment tree but with a smaller memory footprint and a notably simpler implementation, at the cost of being specialized for a narrower set of operations — mainly sums (and other invertible operations) rather than arbitrary range queries like minimum or maximum.

The problem it solves

Say you have an array of numbers and need to repeatedly do two things: update a single element, and ask for the sum of a range of elements. A naive approach makes one of these operations slow:

• Recomputing the sum on every query by iterating the range is O(n) per query.
• Precomputing a prefix-sum array makes queries O(1), but every update requires recalculating all prefix sums after the changed index — also O(n).

Neither works well when updates and range-sum queries are interleaved and frequent — a running leaderboard, a frequency table, cumulative statistics over a stream of events. A Fenwick tree gets both operations down to O(log n), which is fast enough that millions of interleaved updates and queries run comfortably.

How it works

The trick is indexing. A Fenwick tree stores the same n elements as the original array, but each index i in the tree holds the sum of a specific range ending at i, where the range’s length is determined by the lowest set bit of i in binary — a value computable as i & (-i).

This layout means:

• Point update: to add a value at index i, update the tree at i, then repeatedly jump to i + (i & -i) and update again, until you run past the array’s end. Each jump climbs to the next node whose range covers the updated index — O(log n) hops.
• Prefix-sum query: to sum everything from index 1 to i, start at i, add the tree’s value there, then repeatedly jump to i - (i & -i) and add again, until reaching 0. Again O(log n) hops.
• Range sum (from l to r) is just prefixSum(r) - prefixSum(l - 1), using the same query twice.

The whole implementation is typically under twenty lines — a single array and two small loops using bitwise operations, no pointers, no recursive tree traversal.

tree = array of size n+1, initialized to 0

function update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & (-i)

function prefixSum(i):
    sum = 0
    while i > 0:
        sum += tree[i]
        i -= i & (-i)
    return sum

Fenwick tree vs segment tree

Both structures answer range queries with logarithmic updates, and it’s a fair question which one to reach for.

	Fenwick tree	Segment tree
Memory	One array, size n	Typically 2n to 4n
Code complexity	~20 lines, iterative	More involved, often recursive
Supported queries	Sum, and other invertible operations (XOR, product)	Any associative operation — min, max, GCD, sum
Range updates	Possible with extensions, less natural	Naturally supports with lazy propagation
Best for	Prefix sums and frequency counts	General range queries, including min/max

The deciding factor is usually the operation. If the query is a sum (or another operation with an inverse, like XOR), a Fenwick tree is simpler and faster to write correctly under time pressure. If the query is a minimum, maximum, or anything without a clean inverse, a segment tree is the right tool — you can’t “subtract” a maximum the way you can subtract a sum, which is exactly what the Fenwick tree’s query logic relies on.

Why the bit trick works

The i & (-i) operation isolates the lowest set bit of i — for i = 12 (binary 1100), i & (-i) gives 4 (binary 0100). This is a consequence of how two’s-complement negation works: negating a number flips all bits and adds one, which cascades through trailing zeros and flips the lowest set bit’s neighbors in a way that, when ANDed with the original, leaves only that bit standing. Big-endian and little-endian byte order don’t affect this — it’s purely a matter of bit position within a single integer, not byte layout — but understanding two’s complement is worth a look if the trick feels like magic; see big-endian vs little-endian for related bit-representation concepts and what is Big-O notation for why “index range halves roughly every jump” translates directly into the O(log n) bound.

Each index’s implicit range size — determined by that lowest set bit — is why the structure is sometimes visualized as an implicit binary tree layered over a flat array, even though there are no explicit node or pointer structures at all, unlike a binary search tree or a heap, both of which need explicit parent-child links or array-index arithmetic tied to a tree shape.

Common use cases

• Competitive programming, where its small code footprint and reliability under time pressure make it a default choice for prefix-sum problems.
• Frequency tables and order statistics, such as counting how many values seen so far are less than a given value (a “count of inversions” problem).
• Cumulative counters in analytics or leaderboard systems, where individual counts update frequently and range totals are queried often.
• 2D extensions (a Fenwick tree of Fenwick trees) for 2D range-sum queries, at the cost of O(log² n) per operation instead of O(log n).

The takeaway

A Fenwick tree trades generality for simplicity: it only handles operations with an inverse, chiefly sums, but does so with a single flat array, no pointers, and a handful of bitwise operations per call. For prefix-sum and point-update workloads it beats a segment tree on both memory and implementation risk; for anything needing min, max, or other non-invertible range queries, a segment tree remains the right choice.