7.21 Fenwick Trees

A Fenwick tree, also called a binary indexed tree, is a compact data structure for prefix sums and point updates.

It solves a narrower problem than a segment tree, but it solves that problem with less code, less memory, and excellent constant factors. If your operation is sum-like and your updates affect one position at a time, a Fenwick tree is often the cleanest choice.

The structure is built on a clever indexing rule. Each internal slot stores the sum of a range whose size is determined by the least significant set bit of the index.

Problem

Given an array:

[2, 4, 5, 7, 8]

support:

Add delta to one index
Find prefix sum from 0 to i
Find range sum from left to right

A prefix-sum array answers queries in O(1), but updates cost O(n).

A segment tree supports both in O(log n), but it uses more memory and more code.

A Fenwick tree gives a smaller specialized solution.

Solution

Store partial sums in an auxiliary array indexed from 1.

type Fenwick struct {
	tree []int
}

Create a tree with n elements:

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

The extra slot at index 0 is unused. This makes bit operations simpler.

The Key Operation

Fenwick trees rely on:

i & -i

This expression extracts the least significant set bit of i.

Examples:

i = 1  -> 1
i = 2  -> 2
i = 3  -> 1
i = 4  -> 4
i = 6  -> 2
i = 8  -> 8

That value tells the tree how large a range is represented by a given index.

For index i, tree[i] stores a sum over:

i - lowbit(i) + 1
through
i

using one-based indexing.

Range Responsibility

Suppose the array has eight elements.

The Fenwick tree slots cover these ranges:

tree[1] -> [1,1]
tree[2] -> [1,2]
tree[3] -> [3,3]
tree[4] -> [1,4]
tree[5] -> [5,5]
tree[6] -> [5,6]
tree[7] -> [7,7]
tree[8] -> [1,8]

The ranges are not arbitrary. They are determined entirely by the binary representation of each index.

This is why Fenwick trees are compact and fast.

Point Update

To add a value at an index, update every Fenwick slot whose range includes that index.

func (f *Fenwick) Add(index int, delta int) {
	index++

	for index < len(f.tree) {
		f.tree[index] += delta
		index += index & -index
	}
}

The public index is zero-based.

Internally, the tree uses one-based indexing, so the function increments index first.

Example:

fw := NewFenwick(5)

fw.Add(0, 2)
fw.Add(1, 4)
fw.Add(2, 5)
fw.Add(3, 7)
fw.Add(4, 8)

This builds the logical array:

[2, 4, 5, 7, 8]

Prefix Sum

To compute the prefix sum through index i, walk backward through responsible ranges.

func (f *Fenwick) PrefixSum(index int) int {
	index++
	sum := 0

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

	return sum
}

Example:

fmt.Println(fw.PrefixSum(3))

Output:

because:

2 + 4 + 5 + 7 = 18

Range Sum

A range sum is the difference between two prefix sums.

func (f *Fenwick) RangeSum(left int, right int) int {
	if left == 0 {
		return f.PrefixSum(right)
	}

	return f.PrefixSum(right) -
		f.PrefixSum(left-1)
}

Example:

fmt.Println(fw.RangeSum(1, 3))

Output:

because:

4 + 5 + 7 = 16

Why Prefix Queries Work

Consider a prefix ending at one-based index 7.

Binary form:

7 = 111₂

Fenwick traversal:

7 -> 6 -> 4 -> 0

The ranges are:

tree[7] -> [7,7]
tree[6] -> [5,6]
tree[4] -> [1,4]

Together:

[1,4] + [5,6] + [7,7]

covers:

[1,7]

exactly once.

This decomposition is the heart of the data structure.

Why Updates Work

When updating one-based index 3, the loop visits:

3 -> 4 -> 8 -> ...

Those are exactly the Fenwick slots whose stored ranges include index 3.

For n = 8:

tree[3] -> [3,3]
tree[4] -> [1,4]
tree[8] -> [1,8]

Adding the delta to each slot keeps future prefix queries correct.

Building from an Array

The simplest build inserts each value.

func BuildFenwick(nums []int) *Fenwick {
	fw := NewFenwick(len(nums))

	for i, v := range nums {
		fw.Add(i, v)
	}

	return fw
}

This costs:

O(n log n)

A linear-time build is also possible.

func BuildFenwickLinear(nums []int) *Fenwick {
	fw := NewFenwick(len(nums))

	for i, v := range nums {
		idx := i + 1
		fw.tree[idx] += v

		parent := idx + (idx & -idx)

		if parent < len(fw.tree) {
			fw.tree[parent] += fw.tree[idx]
		}
	}

	return fw
}

This costs:

O(n)

The linear build is useful when constructing from a full initial array.

Updating a Value

The Add method applies a delta.

If you want to assign a new value, store the original array or query the current value.

func (f *Fenwick) Set(
	values []int,
	index int,
	value int,
) {
	delta := value - values[index]
	values[index] = value
	f.Add(index, delta)
}

The Fenwick tree itself does not directly know individual values unless you store them separately.

Frequency Tables

Fenwick trees are excellent for dynamic frequency counts.

Suppose values lie in:

1..100000

You can store counts by value.

fw.Add(value, 1)

Then:

fw.PrefixSum(x)

returns the number of inserted values less than or equal to x.

This supports:

rank queries
count values in range
dynamic histograms

efficiently.

Order Statistics

With a frequency Fenwick tree, you can find the smallest value whose prefix count reaches k.

This answers:

Find the k-th smallest value

in logarithmic time using binary lifting over the Fenwick tree.

func (f *Fenwick) LowerBound(target int) int {
	idx := 0
	bit := 1

	for bit*2 < len(f.tree) {
		bit *= 2
	}

	for bit > 0 {
		next := idx + bit

		if next < len(f.tree) &&
			f.tree[next] < target {

			idx = next
			target -= f.tree[next]
		}

		bit /= 2
	}

	return idx
}

The returned index is zero-based under the usual one-based internal layout.

This technique is useful in inversion counting, online medians, ranking systems, and compressed-coordinate problems.

Inversion Counting

An inversion is a pair:

i < j and nums[i] > nums[j]

Example:

[3, 1, 2]

Inversions:

(3, 1)
(3, 2)

A Fenwick tree can count inversions by scanning left to right and tracking how many previous values are greater than the current value.

This requires coordinate compression when values are large.

Coordinate Compression

Fenwick tree indexes must be compact integers.

If values are:

1000000000
-50
42

compress them to ranks:

-50 -> 0
42 -> 1
1000000000 -> 2

The Fenwick tree then operates on ranks rather than raw values.

This pattern appears frequently in ordered counting problems.

Fenwick Trees Versus Segment Trees

Feature	Fenwick Tree	Segment Tree
Prefix sums	Excellent	Good
Range sums	Excellent	Good
Point updates	Excellent	Good
Range min/max	Limited	Excellent
Memory	O(n)	O(4n) common
Code size	Small	Larger
Flexibility	Moderate	High

Use Fenwick trees when sums or counts are enough.

Use segment trees when the aggregate or update model is more complex.

Complexity Analysis

For n elements:

Operation	Complexity
Build by repeated add	O(n log n)
Linear build	O(n)
Point update	O(log n)
Prefix sum	O(log n)
Range sum	O(log n)
Lower bound on prefix sums	O(log n)
Space	O(n)

The constants are small because the implementation uses simple array indexing and bit operations.

Common Mistakes

A common mistake is mixing zero-based and one-based indexing. The public API can be zero-based, but the internal tree should usually be one-based.

Another mistake is using a Fenwick tree for arbitrary range minimum queries. The structure is primarily designed for invertible prefix aggregates such as sums.

A third mistake is forgetting that assignment requires a delta. Store the original values if you need Set.

Finally, coordinate compression is required when values are large, negative, or sparse.

Takeaway

Fenwick trees provide a compact and efficient solution for dynamic prefix sums, range sums, frequency counts, ranks, and order statistics. They achieve logarithmic updates and queries using only an array and a small bit operation. Compared with segment trees, they are less general but simpler and often faster. When the problem involves sums, counts, or prefix-based reasoning, a Fenwick tree should be one of the first structures considered.