8.14 Fenwick Trees

Not every range-query problem requires the full power of a Segment Tree.

algorithmstreesdata-structures

8.14 Fenwick Trees

Not every range-query problem requires the full power of a Segment Tree.

Many practical workloads involve only two operations:

  • Update a single value.
  • Query a prefix sum.

Examples include:

  • Running totals
  • Frequency counts
  • Event counters
  • Rankings
  • Histogram maintenance
  • Subtree sums after Euler Tour flattening

For these cases, a Fenwick Tree provides an elegant alternative. It uses less memory, requires less code, and often performs better in practice because of its compact representation.

The Fenwick Tree, also known as a Binary Indexed Tree (BIT), is one of the most useful data structures for cumulative-frequency problems.

Problem

You need efficient updates and sum queries on an array.

Operations:

add(index, value)
sum(left, right)

A naive implementation scans the affected range.

With many updates and queries, performance degrades quickly.

Solution

Store partial sums in a Binary Indexed Tree.

Consider:

Index: 1 2 3 4 5 6 7 8
Value: 5 2 7 1 4 3 8 6

A Fenwick Tree stores selected cumulative ranges.

Instead of storing every interval explicitly, it uses binary properties of indices to determine which ranges each entry represents.

Implementation:

package main

type Fenwick struct {
    tree []int
}

func NewFenwick(n int) *Fenwick {
    return &Fenwick{
        tree: make([]int, n+1),
    }
}

The structure uses one-based indexing.

This simplifies the bit manipulations that make the data structure work.

Discussion

The most important operation in a Fenwick Tree is:

index & -index

This expression extracts the least significant set bit.

Examples:

Index Binary index & -index
1 0001 1
2 0010 2
3 0011 1
4 0100 4
6 0110 2
8 1000 8

This value determines the interval size represented by a node.

For example:

Position Covers
1 [1,1]
2 [1,2]
4 [1,4]
8 [1,8]
6 [5,6]

The structure forms an implicit tree without storing explicit child pointers.

Point Updates

To add a value:

func (f *Fenwick) Add(
    index int,
    delta int,
) {
    for index < len(f.tree) {
        f.tree[index] += delta
        index += index & -index
    }
}

Example:

bit.Add(3, 7)

The update affects all ranges containing position 3.

The bit manipulation automatically identifies those ranges.

For index 3:

3
→ 4
→ 8
→ 16
...

Each affected node receives the update.

Prefix Sums

To compute:

sum(1,index)

move upward through the implicit structure.

func (f *Fenwick) PrefixSum(
    index int,
) int {
    result := 0

    for index > 0 {
        result += f.tree[index]
        index -= index & -index
    }

    return result
}

Example:

bit.PrefixSum(7)

Traversal:

7
→ 6
→ 4
→ 0

The collected intervals exactly cover:

[1,7]

without overlap.

Range Sums

Once prefix sums exist, range sums become simple.

func (f *Fenwick) RangeSum(
    left int,
    right int,
) int {
    return f.PrefixSum(right) -
        f.PrefixSum(left-1)
}

Example:

sum(3,7)

becomes:

prefix(7)
-
prefix(2)

This transformation is one of the most important ideas in cumulative-sum algorithms.

Building a Fenwick Tree

The simplest construction inserts values individually.

bit := NewFenwick(n)

for i, value := range values {
    bit.Add(i+1, value)
}

Complexity:

O(n log n)

A more advanced linear-time construction exists, but the incremental version is usually sufficient and easier to understand.

Visualizing the Structure

Suppose:

Index: 1 2 3 4 5 6 7 8

The intervals look like:

1 -> [1]

2 -> [1,2]

3 -> [3]

4 -> [1,4]

5 -> [5]

6 -> [5,6]

7 -> [7]

8 -> [1,8]

Notice how powers of two represent increasingly larger ranges.

This organization allows logarithmic traversal.

Why the Bit Trick Works

Consider:

index = 12

1100₂

The least significant set bit:

0100₂

equals:

4

Subtracting it:

12 - 4 = 8

moves to the next ancestor interval.

Adding it:

12 + 4 = 16

moves to the next larger covering interval.

The binary representation naturally encodes the tree structure.

No explicit pointers are required.

Frequency Counting

Fenwick Trees are frequently used for frequency tables.

Suppose:

Value
-----
3
1
5
3
2

Store counts:

bit.Add(value, 1)

Now:

How many values ≤ X?

becomes:

bit.PrefixSum(X)

This technique appears in:

  • Ranking systems
  • Order statistics
  • Inversion counting
  • Streaming analytics

Inversion Counting

Consider:

3 1 2

Inversions:

(3,1)
(3,2)

Answer:

2

Process values from left to right.

For each element:

Previously seen values
greater than current

can be computed using Fenwick queries.

The resulting algorithm runs in:

O(n log n)

instead of:

O(n²)

This is one of the classic Fenwick Tree applications.

Euler Tour and Subtree Sums

Fenwick Trees pair naturally with Euler Tours.

Suppose:

Subtree(node)

corresponds to:

[start,end]

in Euler order.

Subtree sum:

bit.RangeSum(start, end)

Point update:

bit.Add(position, delta)

The original tree disappears.

The problem becomes a sequence problem.

This combination appears frequently in competitive programming and large-scale hierarchy systems.

Fenwick Trees vs Prefix Sums

Prefix sums support:

Range query

in:

O(1)

but updates require:

O(n)

recomputation.

Fenwick Trees support:

Query: O(log n)
Update: O(log n)

This tradeoff is often worthwhile when updates occur frequently.

Fenwick Trees vs Segment Trees

Both structures support logarithmic operations.

However, they target different workloads.

Feature Fenwick Tree Segment Tree
Prefix sums Excellent Excellent
Range sums Excellent Excellent
Point updates Excellent Excellent
Range minimum Difficult Natural
Range maximum Difficult Natural
Custom aggregates Limited Flexible
Memory O(n) O(n)
Constant factors Smaller Larger
Implementation Simpler More complex

Fenwick Trees are specialized.

Segment Trees are more general.

When sums are sufficient, Fenwick Trees are often preferable.

Two Fenwick Trees

A surprising extension supports range updates.

Instead of storing:

point changes

store:

difference changes

Using two Fenwick Trees, it becomes possible to perform:

Range update
Range query

in logarithmic time.

The technique relies on the same prefix-sum principles discussed earlier in Chapter 2.

This illustrates how multiple algorithmic ideas often combine into more powerful structures.

Complexity Analysis

Let:

n = number of elements

Operations:

Operation Complexity
Add O(log n)
Prefix sum O(log n)
Range sum O(log n)

Memory:

Structure Complexity
Fenwick Tree O(n)

The logarithmic factor comes from repeatedly removing the least significant set bit.

Each operation visits at most:

O(log n)

indices.

Common Mistakes

A common mistake is using zero-based indexing.

Fenwick Trees are usually implemented with:

1-based indexing

because the bit operations depend on it.

Another mistake is forgetting:

index += index & -index

during updates.

Using subtraction instead of addition moves in the wrong direction.

A third mistake is attempting to compute minimum or maximum values directly. Fenwick Trees naturally support invertible cumulative operations such as addition. Arbitrary aggregates generally require Segment Trees.

Finally, many bugs arise from incorrect interval formulas:

sum(left,right)
=
prefix(right)
-
prefix(left-1)

The subtraction of left-1 is essential.

Takeaway

Fenwick Trees provide an elegant solution for dynamic cumulative-sum problems. By exploiting binary properties of indices, they support updates and prefix queries in logarithmic time while using only linear memory. Although less flexible than Segment Trees, they are simpler, faster, and often the best choice when the primary operation is summation. Combined with Euler Tours, Fenwick Trees become a powerful tool for subtree aggregation and dynamic hierarchy queries.