You have an array of n integers and need to support two operations:

A plain array gives O(1) updates but O(n) prefix sums. A prefix sum array gives O(1) prefix sums but O(n) updates, because every update invalidates the precomputed sums after that index.

The Fenwick Tree (also called Binary Indexed Tree, or BIT) gives O(log n) for both. The entire structure rests on a single operation: i & (-i), which isolates the lowest set bit of i.

A segment tree (covered in the next chapter) can do everything a BIT can do and more, but a BIT uses about half the code and has lower constant factors when the operation is invertible (sum, XOR).

The Problem

Let us frame the trade-off clearly.

With a plain array, updating an element is O(1), but computing a prefix sum requires iterating from index 0 to i, which is O(n).

With a prefix sum array, querying a range sum is O(1), but updating a single element forces you to rebuild part of the prefix array, which is O(n).

What we want is a structure where both operations cost O(log n). The Fenwick Tree delivers exactly that.

The Key Insight: Lowest Set Bit

Every positive integer has a binary representation, and every binary representation has a lowest set bit, the rightmost 1. For example:

The expression i & (-i) isolates this lowest set bit. In two's complement, -i flips all bits of i and adds 1, so i & (-i) zeroes out everything except the rightmost 1. Every update and query in a BIT is built on top of this one operation.

Here is how it works: the lowest set bit of index i determines the responsibility range of that position in the BIT. Position i stores the sum of i & (-i) elements ending at index i.

Responsibility Ranges

The following diagram shows how each BIT position covers a range of the original array (for an array of size 8).

Nodes with larger lowest-set-bit values sit higher in the hierarchy and cover wider ranges. Nodes with a lowest set bit of 1 (odd indices) are always leaves, covering just a single element.

Internal Representation

A Fenwick Tree is stored as a 1-indexed array of size n + 1. Index 0 is unused (or set to 0). 1-indexing is required for the bit trick to terminate: 0 & (-0) = 0, so calling update(0, ...) would loop forever, and query(0) needs to stop at 0.

There is no actual tree object in memory

Unlike a binary tree with explicit pointers or even a heap-style array layout, a Fenwick Tree is just a flat array. The "tree" structure exists only in the parent-child relationship encoded by i & (-i). The parent of index i is i + (i & (-i)), and the elements that contribute to the prefix sum at i are visited by repeatedly subtracting the lowest set bit. The hierarchy in the diagram above is implicit, not stored.

0-based variants exist (using i | (i + 1) and (i & (i + 1)) - 1), but 1-based is the standard convention and the code below uses it throughout.

Point Update: update(i, delta)

To add delta to position i, you walk upward through the tree. Starting at index i, you add delta to BIT[i], then move to the next position by adding the lowest set bit: i += i & (-i). You repeat until i exceeds n.

Why does this work? Every position j that is responsible for a range containing index i must be updated. The "add lowest set bit" operation visits exactly those positions, climbing from narrow ranges to wider ones.

Starting at index 3 (binary 011), the lowest set bit is 1, so we jump to 3 + 1 = 4. At index 4 (binary 100), the lowest set bit is 4, so we jump to 4 + 4 = 8. At index 8, if this is the last valid index, we stop. Only 3 positions were touched for an array of size 8, which is log2(8) = 3.

Prefix Query: query(i)

To compute the prefix sum from index 1 to i, you walk downward. Starting at index i, you accumulate BIT[i] into a running sum, then move to the next position by subtracting the lowest set bit: i -= i & (-i). You repeat until i reaches 0.

The intuition for the two directions

Every position i is contained in exactly the responsibility ranges of the nodes visited by repeatedly adding the lowest set bit (those are the BIT positions whose range covers index i, so an update at i must touch all of them). And the prefix [1..i] decomposes into exactly the disjoint responsibility ranges of the nodes visited by repeatedly subtracting the lowest set bit (stripping the lowest 1-bit hops back to the previous range boundary).

Updates walk up; queries walk down. Both visit O(log n) positions because each step either sets or clears a single bit, and there are at most log n bits.

To compute the prefix sum up to index 7, we visit BIT[7] (covers a[7]), then BIT[6] (covers a[5..6]), then BIT[4] (covers a[1..4]). Adding those three stored values gives us a[1] + a[2] + ... + a[7]. Again, only 3 lookups for an 8-element array.

Range Query: rangeQuery(l, r)

A range sum from index l to r is simply query(r) - query(l - 1). This follows the same logic as prefix sum arrays: the sum of elements in [l, r] equals the prefix sum up to r minus the prefix sum up to l - 1.

Building the BIT: O(n) Approach

You could build a BIT by calling update for each element, but that gives O(n log n). There is a cleaner O(n) approach: copy the original array into the BIT array, then for each index i from 1 to n, propagate BIT[i] to its parent j = i + (i & (-i)) (if j <= n). A single forward pass suffices because parents always have a higher index than children, so by the time we reach i in the loop, BIT[i] already contains the full sum of its responsibility range.

Let us work through a concrete example with the array a = [1, 3, 5, 7, 2, 4, 6, 8] (8 elements, 1-indexed).

Step 1: Building the BIT

We start by copying the array into BIT positions 1 through 8, then propagating each position to its parent.

Let us verify a few values:

Step 2: Querying Prefix Sum Up to Index 6

We want query(6), which should return a[1] + a[2] + a[3] + a[4] + a[5] + a[6] = 1 + 3 + 5 + 7 + 2 + 4 = 22.

Two lookups to sum six elements, instead of six additions.

Step 3: Updating Index 3 by +2

We want to add 2 to a[3], making it 7 instead of 5. This means update(3, 2).

Step 4: Querying Range Sum [3, 6] After the Update

Range sum [3, 6] = query(6) - query(2).

After the update, a = [1, 3, 7, 7, 2, 4, 6, 8], so the expected answer is 7 + 7 + 2 + 4 = 20.

Here is a complete Fenwick Tree implementation. It builds the tree from an array in O(n), supports point updates with update, prefix sums with query, and range sums with rangeQuery, all using the lowest-set-bit idiom on 1-indexed positions.

Code Explanation

The implementation is intentionally simple in structure. Let us walk through the key design decisions.

The constructor performs an O(n) build

Instead of calling update n times (which would be O(n log n)), we copy the array into BIT positions 1 through n, then make a single forward pass. For each index i, we push its value to its parent i + (i & (-i)). Since each element has exactly one parent, this is a linear operation. This is a subtle but important optimization. In an interview, it shows you understand the parent-child relationships in the tree, not just the query/update mechanics.

Update walks upward using i += i & (-i)

Each iteration moves to the next position whose responsibility range includes index i. Because each step at least doubles i (removing the lowest set bit and adding a higher power of 2), the loop runs at most log n times.

Query walks downward using i -= i & (-i)

Each iteration strips away the lowest set bit, moving to the next non-overlapping range that contributes to the prefix sum. Since each step reduces i by at least 1 (and each bit can only be stripped once), the loop runs at most log n times.

Range query is a simple difference

This is the same trick as prefix sum arrays: sum(l, r) = prefix(r) - prefix(l-1).

Time Complexity

Both update and query run in O(log n) time. Here is why:

Building the BIT takes O(n) with the propagation approach, or O(n log n) with repeated updates.

Space Complexity

O(n) for the BIT array. Unlike a segment tree (which needs 2n or 4n space), a BIT uses exactly n + 1 elements. This lower space usage also means better cache performance in practice.

Comparison Table

*Range update with a BIT requires the difference array technique (covered in the next section).

For problems that only need prefix sums with point updates, a BIT is the better tool than a segment tree. Reach for a segment tree when you need range min/max or lazy propagation.

Range Update + Point Query

Sometimes you need the opposite pattern: update an entire range [l, r] by adding a value, then query the value at a single point. A BIT handles this using the difference array concept.

Instead of storing actual values, store differences. To add delta to range [l, r]:

To query the value at position i, call query(i). The prefix sum of the difference array gives you the actual value at that position.

This works because adding delta at position l and subtracting it at position r + 1 means the prefix sum from l to r increases by delta, and everything after r cancels out.

2D Fenwick Tree

For problems involving a 2D grid where you need to update individual cells and query rectangular sub-sums, extend the BIT to two dimensions. Each operation becomes a nested loop:

Both operations are O(log n * log m) for an n x m grid. To query any arbitrary rectangle (x1, y1) to (x2, y2), use inclusion-exclusion:

rectSum = query(x2,y2) - query(x1-1,y2) - query(x2,y1-1) + query(x1-1,y1-1)

BIT for Order Statistics

A BIT can answer "how many elements less than x have been inserted so far?" in O(log n). This is the basis for inversion counting and online rank queries.

The idea: treat the BIT as a frequency array. When you insert a value v, call update(v, 1). To find how many values less than or equal to v have been inserted, call query(v). With coordinate compression (mapping large values to a compact range), this handles arbitrary integer ranges.

Variants Summary

Understanding when to choose a Fenwick Tree versus its alternatives is just as important as knowing how it works.

When to choose a Fenwick Tree:

When NOT to use a Fenwick Tree:

Pattern 1: Inversion Counting

Problem: Given an array, count the number of pairs (i, j) where i < j and a[i] > a[j].

Approach: Process the array from right to left. For each element a[i], query the BIT for "how many elements smaller than a[i] have we already seen?" (these are elements to the right of i that are smaller, meaning a[i] forms an inversion with each of them). Then insert a[i] into the BIT.

This runs in O(n log n), matching merge sort but with a completely different approach.

Pattern 2: Frequency Counting with Coordinate Compression

Many problems give you large value ranges (up to 10^9) but small array sizes (up to 10^5). You cannot create a BIT of size 10^9, but you can compress the values to the range [1, n] while preserving their relative order. This is called coordinate compression, and it pairs perfectly with BITs.

The steps are:

This pattern appears in problems like "count of smaller numbers after self" and "count of range sum."

Pattern 3: Dynamic Cumulative Sums

Any time you have a running stream of values and need to answer prefix/range sum queries interspersed with updates, a BIT is the natural choice. This comes up in: