Fenwick Tree (Binary Indexed Tree)

A Fenwick tree answers “prefix sum up to index ii” and “add deltadelta at index ii” in $O(\log n)$ each, using one flat array and a single bitwise trick — no recursion, no explicit tree nodes, and about fifteen lines of code.

What you’ll learn

The lowbit trick, i & (-i)i & (-i), and why it isolates the lowest set bit of ii.
How that one trick gives $O(\log n)$ point update and $O(\log n)$ prefix-sum query.
Getting an arbitrary range sum from two prefix queries.
Why a Fenwick tree is simpler but less general than a segment tree, and when to reach for which.
A brief look at extending it to 2D.

The lowbit trick: `i & (-i)i & (-i)`

Every positive integer, in two’s-complement binary, has the property that i & (-i)i & (-i) isolates its lowest set bit — the smallest power of two that divides it:

lowbit.py

def lowbit(i):
    return i & (-i)
 
 
for i in [1, 2, 3, 4, 6, 12, 24]:
    print(f"i={i:>2} ({i:>05b})  lowbit={lowbit(i)}")

lowbit.py

def lowbit(i):
    return i & (-i)
 
 
for i in [1, 2, 3, 4, 6, 12, 24]:
    print(f"i={i:>2} ({i:>05b})  lowbit={lowbit(i)}")

text

>>> bin(12)
'0b1100'
>>> lowbit = 12 & (-12)
>>> lowbit
4
>>> bin(lowbit)
'0b100'

text

>>> bin(12)
'0b1100'
>>> lowbit = 12 & (-12)
>>> lowbit
4
>>> bin(lowbit)
'0b100'

Every Fenwick tree index ii (the tree is conventionally 1-indexed) is made “responsible” for summing exactly lowbit(i)lowbit(i) elements, ending at ii itself:

Index `ii`	`lowbit(i)lowbit(i)`	Range it’s responsible for
1	1	`[1, 1][1, 1]`
2	2	`[1, 2][1, 2]`
3	1	`[3, 3][3, 3]`
4	4	`[1, 4][1, 4]`
5	1	`[5, 5][5, 5]`
6	2	`[5, 6][5, 6]`
7	1	`[7, 7][7, 7]`
8	8	`[1, 8][1, 8]`

Connecting each index ii to i + lowbit(i)i + lowbit(i) (the index that will next need to know about a change at ii) turns this table into an actual tree:

diagram Fenwick tree structure for n=8 -- edges follow i += lowbit(i), the update-chain jump mermaid

  graph BT
    N1["1: owns [1,1]"] --> N2["2: owns [1,2]"]
    N2 --> N4["4: owns [1,4]"]
    N3["3: owns [3,3]"] --> N4
    N5["5: owns [5,5]"] --> N6["6: owns [5,6]"]
    N6 --> N8["8: owns [1,8]"]
    N7["7: owns [7,7]"] --> N8
    N4 --> N8

Update walks up this tree (i += lowbit(i)i += lowbit(i), toward the root) to touch every ancestor whose range includes ii. Query walks down — really, it walks toward 00 (i -= lowbit(i)i -= lowbit(i)), accumulating sums from disjoint ranges that together cover [1, i][1, i].

sketch Update chain (amber, walks up) vs. prefix-sum chain (blue, walks toward 0) p5.js

update(3) touches 3 -> 4 -> 8. prefix_sum(6) touches 6 -> 4, then stops at 0.

Build, update, and query

fenwick_tree.py

class FenwickTree:
    """1-indexed Binary Indexed Tree: O(log n) point update, O(log n) prefix-sum query."""
 
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # tree[0] is unused -- indices are 1..n
 
    def update(self, i, delta):
        """Add `delta` to the value at position i (1-indexed)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)          # walk UP to the next index this one feeds into
 
    def prefix_sum(self, i):
        """Sum of elements 1..i (1-indexed, inclusive)."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)          # walk toward 0, one disjoint range at a time
        return total
 
    def range_sum(self, left, right):
        """Sum over the inclusive 1-indexed range [left, right]."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)
 
    @classmethod
    def from_list(cls, values):
        """Build in O(n log n) via repeated point updates (simple; an O(n) build exists too)."""
        bit = cls(len(values))
        for i, v in enumerate(values, start=1):
            bit.update(i, v)
        return bit
 
 
values = [3, 2, -1, 6, 5, 4, -3, 3]     # conceptually 1-indexed: position 1..8
bit = FenwickTree.from_list(values)
 
print("sum of first 5 elements:", bit.prefix_sum(5))         # 3+2-1+6+5 = 15
print("sum of elements 3..6:", bit.range_sum(3, 6))          # -1+6+5+4 = 14
 
bit.update(3, 10)                                             # position 3: -1 -> 9
print("sum of elements 3..6 after point update:", bit.range_sum(3, 6))   # 9+6+5+4 = 24

fenwick_tree.py

class FenwickTree:
    """1-indexed Binary Indexed Tree: O(log n) point update, O(log n) prefix-sum query."""
 
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # tree[0] is unused -- indices are 1..n
 
    def update(self, i, delta):
        """Add `delta` to the value at position i (1-indexed)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)          # walk UP to the next index this one feeds into
 
    def prefix_sum(self, i):
        """Sum of elements 1..i (1-indexed, inclusive)."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)          # walk toward 0, one disjoint range at a time
        return total
 
    def range_sum(self, left, right):
        """Sum over the inclusive 1-indexed range [left, right]."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)
 
    @classmethod
    def from_list(cls, values):
        """Build in O(n log n) via repeated point updates (simple; an O(n) build exists too)."""
        bit = cls(len(values))
        for i, v in enumerate(values, start=1):
            bit.update(i, v)
        return bit
 
 
values = [3, 2, -1, 6, 5, 4, -3, 3]     # conceptually 1-indexed: position 1..8
bit = FenwickTree.from_list(values)
 
print("sum of first 5 elements:", bit.prefix_sum(5))         # 3+2-1+6+5 = 15
print("sum of elements 3..6:", bit.range_sum(3, 6))          # -1+6+5+4 = 14
 
bit.update(3, 10)                                             # position 3: -1 -> 9
print("sum of elements 3..6 after point update:", bit.range_sum(3, 6))   # 9+6+5+4 = 24

range_sumrange_sum is where the “invertible” requirement shows up: sum(right) - sum(left - 1)sum(right) - sum(left - 1) only works because subtraction can undo addition. There’s no equivalent trick for minmin or maxmax — you can’t “subtract” a minimum back out of a combined range — which is exactly why a Fenwick tree can’t replace a segment tree for those operations.

Fenwick tree vs. segment tree

Aspect	Fenwick tree (BIT)	Segment tree
Code size	~15 lines, no recursion	~40-60 lines
Supported operations	Invertible ops only (sum, xor)	Any associative op (sum, min, max, gcd, custom)
Range update + range query	Awkward (needs a second BIT)	Native, via lazy propagation
Memory	`n + 1n + 1` ints	`~2n~2n` (iterative) to `~4n~4n` (recursive)
Conceptual overhead	One bitwise trick	Tree recursion + merge/identity abstraction

When the operation is a plain sum (or xor) and only one of “range update” / “range query” is ever a range (the other being a point), the Fenwick tree wins on simplicity every time.

A quick look at 2D

The same lowbit trick nests cleanly into two dimensions: update and query both become a double loop, one lowbit walk per axis.

fenwick_tree_2d.py

class FenwickTree2D:
    """2D BIT: point update + prefix-rectangle-sum query, O(log rows * log cols) each."""
 
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
 
    def update(self, r, c, delta):
        i = r
        while i <= self.rows:
            j = c
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
 
    def prefix_sum(self, r, c):
        """Sum of the rectangle from (1, 1) to (r, c), inclusive, 1-indexed."""
        total = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total
 
 
grid = FenwickTree2D(4, 4)
grid.update(2, 3, 5)   # point (2,3) += 5
grid.update(4, 4, 7)   # point (4,4) += 7
 
print("prefix sum up to (3, 3):", grid.prefix_sum(3, 3))   # only (2,3) is inside -> 5
print("prefix sum up to (4, 4):", grid.prefix_sum(4, 4))   # both points inside -> 12

fenwick_tree_2d.py

class FenwickTree2D:
    """2D BIT: point update + prefix-rectangle-sum query, O(log rows * log cols) each."""
 
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
 
    def update(self, r, c, delta):
        i = r
        while i <= self.rows:
            j = c
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
 
    def prefix_sum(self, r, c):
        """Sum of the rectangle from (1, 1) to (r, c), inclusive, 1-indexed."""
        total = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total
 
 
grid = FenwickTree2D(4, 4)
grid.update(2, 3, 5)   # point (2,3) += 5
grid.update(4, 4, 7)   # point (4,4) += 7
 
print("prefix sum up to (3, 3):", grid.prefix_sum(3, 3))   # only (2,3) is inside -> 5
print("prefix sum up to (4, 4):", grid.prefix_sum(4, 4))   # both points inside -> 12

The same “subtract off what shouldn’t be counted” idea from 1D range sums extends to rectangles too (inclusion-exclusion over four prefix queries), which is exactly the shape of Range Sum Query 2D - Mutable.

Complexity

Operation	Time
Build (via `nn` point updates)	$O(n \log n)$
Point update	$O(\log n)$
Prefix-sum query	$O(\log n)$
Range-sum query (two prefix queries)	$O(\log n)$
2D point update / prefix query	$O(\log(\text{rows}) \cdot \log(\text{cols}))$

Practice — real LeetCode problems

The first is the Fenwick tree with nothing added. The other two are the trick that makes it a competitive-programming staple: index by rank, store counts, and a prefix sum becomes “how many values below this one have I seen”.

LC 307 — Range Sum Query - Mutable · Medium

Problem. Implement NumArray(nums)NumArray(nums) with update(index, val)update(index, val) setting an element and sumRange(left, right)sumRange(left, right) returning the inclusive sum.

Constraints. 1 <= len(nums) <= 3 * 10**41 <= len(nums) <= 3 * 10**4, -100 <= nums[i], val <= 100-100 <= nums[i], val <= 100, up to 3 * 10**43 * 10**4 calls.

Examples. NumArray([1,3,5])NumArray([1,3,5]): sumRange(0,2)sumRange(0,2) gives 99, then update(1,2)update(1,2), then sumRange(0,2)sumRange(0,2) gives 88

Editorial · approach, complexity, follow-ups

The problem exists to make you choose a structure. A plain array gives $O(1)$ update and $O(n)$ query; a prefix-sum array gives $O(1)$ query and $O(n)$ update. With both operations called $3 \times 10^4$ times, either is $10^9$ operations. A Fenwick tree makes both $O(\log n)$ .

Time $O(n \log n)$ to build, $O(\log n)$ per operation. Space $O(n)$ .

updateupdate sets, it does not add. Storing the current values and applying val - self.nums[index]val - self.nums[index] is the whole adaptation. Adding valval directly is the most common wrong answer and it corrupts everything after the first update.
One-indexing is not decoration. i & -ii & -i is 0 when ii is 0, so index 0 would loop forever. Converting with i += 1i += 1 on the way in is why the public interface can stay zero-indexed.
i & -ii & -i is the lowest set bit, so it is the size of the range that node covers. +=+= walks to the next node that includes ii; -=-= walks to the predecessor block. Being able to say what a node covers is what separates understanding from copying.
_prefix(left)_prefix(left), not _prefix(left + 1)_prefix(left + 1), for an inclusive range. Off by one here is silent — it just gives wrong sums.
Building by nn updates is $O(n \log n)$ . The $O(n)$ build exists: fill the tree with the raw values, then for each ii push tree[i]tree[i] into tree[i + (i & -i)]tree[i + (i & -i)]. Worth mentioning.

Follow-ups you should expect: “Range update, point query?” — store deltas instead of values: add at leftleft, subtract at right + 1right + 1, and a point query is a prefix sum. “Range update, range query?” — two Fenwick trees, or a segment tree with lazy propagation. “Range minimum instead of sum?” — a Fenwick tree cannot do it cleanly, because minmin has no inverse and prefix subtraction is meaningless; use a segment tree. That contrast is the most-asked question about Fenwick trees. “2D?” — nested trees, $O(\log^2 n)$ per operation.

LC 315 — Count of Smaller Numbers After Self · Hard

Problem. Return an array countscounts where counts[i]counts[i] is the number of elements to the right of nums[i]nums[i] that are smaller than it.

Constraints. 1 <= len(nums) <= 10**51 <= len(nums) <= 10**5, -10**4 <= nums[i] <= 10**4-10**4 <= nums[i] <= 10**4.

Examples. [5,2,6,1][5,2,6,1] gives [2,1,1,0][2,1,1,0] · [-1][-1] gives [0][0] · [-1,-1][-1,-1] gives [0,0][0,0]

Editorial · approach, complexity, follow-ups

The reframing is the lesson: a Fenwick tree does not have to store the array. Here the index is a value’s rank and the cell is a count, so prefix(r - 1)prefix(r - 1) answers “how many of the values I have inserted so far are smaller than this one”. Sweeping right to left means “inserted so far” is exactly “to the right of me”.

Time $O(n \log n)$ . Space $O(n)$ .

Coordinate compression is mandatory. Values are negative and the range is 20,001 wide — workable here by shifting, but the habit generalises to values up to $10^9$ where an array indexed by value is impossible.
prefix(r - 1)prefix(r - 1), not prefix(r)prefix(r). Strictly smaller excludes equal values, which is why [-1,-1][-1,-1] must give [0,0][0,0] and not [1,0][1,0].
Right to left. Sweeping the other way answers a different question (smaller numbers before self), and you would have to reverse and re-derive.
Query before insert. Inserting first would count the element against itself.
A single element gives [0][0] — nothing is to its right.

Three other solutions worth naming, because interviewers often want an alternative: merge sort counting inversions during the merge, a balanced BST / order statistic tree, and in Python a SortedListSortedList with bisect_leftbisect_left, which is $O(n \sqrt{n})$ but three lines long and usually fast enough. Say the Fenwick version is what you would write and the SortedListSortedList is what you would reach for under time pressure.

Follow-ups you should expect: “Count greater to the right?” — query the suffix instead, or negate the values. “Count smaller to the left?” — sweep the other way. “Count of Range Sum (LC 327)?” — the same technique over prefix sums instead of raw values. “Reverse Pairs (LC 493)?” — also this, with a doubled comparison. “Streaming input?” — Fenwick handles it directly, since inserts are incremental.

LC 1649 — Create Sorted Array through Instructions · Hard

Problem. Insert the elements of instructionsinstructions one at a time into a new container, keeping it sorted. The cost of each insertion is the minimum of the number of elements already present that are strictly less than it and the number strictly greater. Return the total cost modulo 10**9 + 710**9 + 7.

Constraints. 1 <= len(instructions) <= 10**51 <= len(instructions) <= 10**5, 1 <= instructions[i] <= 10**51 <= instructions[i] <= 10**5.

Examples. [1,5,6,2][1,5,6,2] gives 11 · [1,2,3,6,5,4][1,2,3,6,5,4] gives 33 · [1,3,3,3,2,4,2,1,2][1,3,3,3,2,4,2,1,2] gives 44

Editorial · approach, complexity, follow-ups

The same count-by-rank Fenwick tree as the previous problem, sweeping left to right because “already inserted” now means “earlier in the instruction list”.

The arithmetic that carries the whole problem: after kk insertions, prefix(v)prefix(v) counts everything <= v<= v, so

$\text{greater} = k - \text{prefix}(v), \qquad \text{smaller} = \text{prefix}(v-1)$

and the duplicates — the values exactly equal to vv — are excluded from both, as the definition of cost requires.

Time $O(n \log M)$ where $M$ is the maximum value. Space $O(M)$ .

Duplicates are the whole difficulty. [1,3,3,3,2,4,2,1,2][1,3,3,3,2,4,2,1,2] gives 4, and it is the only test here that distinguishes a correct duplicate rule from k - prefix(v - 1)k - prefix(v - 1), which would count equal elements as greater.
No coordinate compression needed, since values are 1..10**51..10**5. Compressing anyway is harmless and would be required if the bound were $10^9$ .
kk is the count already inserted, which enumerateenumerate gives for free — at iteration kk exactly kk items are in the container.
Modulus at the end, not inside. min(smaller, larger)min(smaller, larger) must be compared on true values; reducing mid-loop cannot change these magnitudes in Python, but taking the modulus before a comparison is a real bug pattern in languages that overflow, and worth flagging.
A single instruction costs 0 — nothing is present to compare against.

Follow-ups you should expect: “Values up to $10^9$ ?” — compress first. “Cost = number of inversions created instead?” — that is LC 315’s count, without the minmin. “Report the running cost after each insertion?” — accumulate and emit; no change to the structure. “Use a SortedListSortedList?” — bisect_leftbisect_left and bisect_rightbisect_right give both counts in $O(\log n)$ with $O(n)$ insertion, which passes here and is far shorter. “Why is minmin there at all?” — it models inserting from whichever end is closer, which is what makes the problem interesting rather than just an inversion count.

LeetCode problem set

#	Problem	Difficulty	The twist
307	Range Sum Query - Mutable	Medium	The same problem as the segment tree lesson, solvable here in far fewer lines
315	Count of Smaller Numbers After Self	Hard	A Fenwick tree over coordinate-compressed values, counting smaller elements seen so far while scanning right to left
1649	Create Sorted Array through Instructions	Hard	Insert one element at a time, using a Fenwick tree over compressed values to count “how many smaller” and “how many larger” already-inserted elements in $O(\log n)$
673	Number of Longest Increasing Subsequence	Medium	A Fenwick-tree variant (indexed by value, storing “best length” / “count of ways” pairs) that answers each element’s transition in $O(\log n)$ instead of the classic $O(n^2)$ DP

Recap

i & (-i)i & (-i) isolates the lowest set bit of ii — the size of the range index ii is responsible for.
Update walks up (i += lowbit(i)i += lowbit(i)); prefix query walks toward zero (i -= lowbit(i)i -= lowbit(i)); both are $O(\log n)$ .
Range sum is just two prefix queries subtracted, which only works because addition is invertible — min/max can’t do this, which is the Fenwick tree’s one real limitation next to a segment tree.
A 2D Fenwick tree nests the same trick along both axes for rectangle sums, at $O(\log(\text{rows}) \cdot \log(\text{cols}))$ per operation.

Between this lesson and the previous one, the segment tree and the Fenwick tree cover almost every “range query + update” problem competitive programming throws at you — reach for the Fenwick tree first when the operation is a plain sum, and the segment tree when it isn’t (or when range updates and range queries both need to be ranges).

Next: Sparse Tables and Range Minimum Query — when the array is static (no updates at all), an even faster $O(1)$ -per-query structure becomes possible.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Fenwick Tree (Binary Indexed Tree)

What you’ll learn

The lowbit trick: i & (-i)i & (-i)

Build, update, and query

Fenwick tree vs. segment tree

A quick look at 2D

Complexity

Practice — real LeetCode problems

LC 307 — Range Sum Query - Mutable · Medium

LC 315 — Count of Smaller Numbers After Self · Hard

LC 1649 — Create Sorted Array through Instructions · Hard

LeetCode problem set

Recap

Was this page helpful?

The lowbit trick: `i & (-i)i & (-i)`