Fenwick Tree (Binary Indexed Tree)

Learn Fenwick Tree (Binary Indexed Tree) with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Fenwick Tree?

A Fenwick Tree is a data structure designed to efficiently calculate prefix-based aggregate values while supporting updates to individual elements. It is also known as a Binary Indexed Tree (BIT).

A Fenwick Tree is commonly used for prefix sum queries, point updates, and range sum queries. Both updating an element and calculating a prefix sum can be performed in O(log n) time.

Unlike a Segment Tree, a Fenwick Tree uses a compact array representation and relies on the binary representation of indexes to determine which portions of the original array each position stores.

Why Do We Need a Fenwick Tree?

Imagine an array that changes frequently while an application repeatedly asks for the sum of elements from the beginning of the array up to a particular index. 

[2, 4, 6, 8, 10, 12]

A prefix sum query such as: 

sum(0, 4)

2 + 4 + 6 + 8 + 10 = 30

can be answered efficiently with a prefix sum array. However, if one of the original values changes, several prefix sums may also need to change. A Fenwick Tree provides a way to support both updates and prefix queries efficiently.

Fenwick Tree and Binary Indexed Tree

The terms Fenwick Tree and Binary Indexed Tree refer to the same data structure. The name Binary Indexed Tree comes from the way the structure uses the binary representation of array indexes.

A Fenwick Tree does not store every prefix sum directly. Instead, each position stores the sum of a specific range of elements. These ranges are determined by the index's lowest set bit.

The Core Idea

Consider the array: 

Index:  1  2  3  4  5  6  7  8
Value:  2  4  6  8 10 12 14 16

A Fenwick Tree stores partial sums rather than storing the original values in exactly the same way as the input array.

For example, depending on the index: 

BIT[1] → value covering index 1
BIT[2] → values covering indexes 1–2
BIT[4] → values covering indexes 1–4
BIT[8] → values covering indexes 1–8

Other indexes represent different smaller intervals. The structure is arranged so that a prefix can be reconstructed by combining a small number of these stored partial sums.

Why Does Fenwick Tree Use 1-Based Indexing?

Fenwick Tree implementations commonly use 1-based indexing. This makes the binary index operations straightforward and allows the lowest set bit to identify the size of the range represented by a tree position.

If the original array uses zero-based indexes, the implementation can internally convert an index using: 

treeIndex = arrayIndex + 1

The Lowest Set Bit

The most important mathematical idea behind a Fenwick Tree is the lowest set bit, often called LSB.

For a positive integer i, its lowest set bit can be extracted using: 

i & -i

For example: 

6 = 110₂

6 & -6 = 2

Lowest set bit = 2

This value determines how far the Fenwick Tree moves during update and prefix-sum operations.

Fenwick Tree Update Operation

The update operation changes the value of one element and updates all Fenwick Tree positions that contain that element in their represented ranges.

Starting from a 1-based index, the algorithm repeatedly adds the lowest set bit to the current index: 

index += index & -index

This moves through the relevant Fenwick Tree nodes that must be updated.

Fenwick Tree Prefix Sum Query

The prefix sum operation calculates the sum from the first element through a specified index.

Starting from the requested index, the algorithm adds the stored value and then moves toward the beginning by subtracting the lowest set bit: 

index -= index & -index

Only a small number of Fenwick Tree positions need to be visited, giving the prefix sum operation O(log n) time complexity.

Range Sum Using a Fenwick Tree

Although the Fenwick Tree is naturally designed around prefix sums, it can also answer a general range sum query.

The sum from index left to index right can be calculated using two prefix sums: 

rangeSum(left, right)
  = prefixSum(right)
  - prefixSum(left - 1)

For example, with: 

[2, 4, 6, 8, 10, 12]

Range: 1 to 4

prefixSum(4) = 30
prefixSum(0) = 2

30 - 2 = 28

Building a Fenwick Tree

A Fenwick Tree can be built by starting with an empty tree and applying each array value as an update. This approach is simple and useful when explaining the data structure.

Another optimized construction method can build the tree in O(n) time. The exact method depends on the implementation and language.

Fenwick Tree Implementation in JavaScript

The following implementation supports point updates, prefix sums, and range sum queries. The internal tree uses one-based indexing while the public methods accept zero-based array indexes.

Fenwick Tree Time Complexity

The main advantage of a Fenwick Tree is its efficient combination of updates and prefix queries.

Operation Time Complexity Space Complexity
Point Update O(log n) O(n)
Prefix Sum O(log n) O(n)
Range Sum O(log n) O(n)

Fenwick Tree vs Prefix Sum Array

A prefix sum array is extremely efficient when the underlying data is static. Once the prefix sums have been calculated, a range sum can be answered in O(1) time.

The problem occurs when an element changes. Updating a prefix sum array can require modifying many values. A Fenwick Tree trades a little query speed for efficient updates.

Structure Range Sum Point Update
Prefix Sum Array O(1) O(n)
Fenwick Tree O(log n) O(log n)

Fenwick Tree vs Segment Tree

Fenwick Trees and Segment Trees are both useful for dynamic range-query problems, but their capabilities and implementations are different.

Feature Fenwick Tree Segment Tree
Point Update O(log n) O(log n)
Range Sum O(log n) O(log n)
Memory O(n) Typically O(n)
Implementation Compact and simpler More involved
Range Operations Best suited to prefix/range aggregates More flexible

A Fenwick Tree is often preferred when the problem mainly requires prefix sums or range sums with point updates. A Segment Tree becomes more useful when the problem requires more complex range operations or additional flexibility.

Advantages of Fenwick Trees

  • Simple implementation compared with many Segment Tree implementations.
  • O(log n) point updates.
  • O(log n) prefix sum queries.
  • O(log n) range sum queries using prefix sums.
  • Uses O(n) memory.
  • Works efficiently with large numbers of updates and queries.
  • Uses a compact array-based representation.

Limitations of Fenwick Trees

  • The implementation relies on understanding binary index operations.
  • It is less flexible than a Segment Tree for complex range operations.
  • Standard implementations are primarily suited to invertible prefix-based operations.
  • Advanced range-update requirements may require specialized Fenwick Tree techniques.
  • Debugging index calculations can be confusing for beginners.

Applications of Fenwick Trees

Fenwick Trees are useful whenever a system needs to maintain cumulative information while individual values are updated.

  • Dynamic prefix sum queries
  • Range sum queries with point updates
  • Frequency tables
  • Counting inversions in arrays
  • Order-statistics style problems
  • Competitive programming problems involving cumulative values
  • Dynamic frequency and counting problems

Counting Frequencies With a Fenwick Tree

A Fenwick Tree does not have to store numerical sums from an application domain. It can also represent frequencies.

For example, if each index represents a value and the tree stores how many times that value has appeared, prefix queries can determine how many values fall within a particular range.

Fenwick Tree for Counting Inversions

A well-known application of the Fenwick Tree is counting inversions in an array. An inversion is a pair of indexes (i, j) where i < j but array[i] > array[j].

By maintaining frequencies and querying how many previously processed values fall within a particular range, a Fenwick Tree can reduce the complexity of inversion-counting approaches from quadratic time to O(n log n), after appropriate value compression when required.

Common Fenwick Tree Mistakes

  • Mixing zero-based and one-based indexes.
  • Forgetting to convert an array index before accessing the tree.
  • Using index += index & -index incorrectly during updates.
  • Using index -= index & -index incorrectly during prefix queries.
  • Forgetting that Fenwick Tree indexes normally start at 1.
  • Using a Fenwick Tree when the required operation needs the flexibility of a Segment Tree.

When Should You Use a Fenwick Tree?

A Fenwick Tree is a good candidate when a problem repeatedly performs point updates and prefix or range aggregate queries. It is particularly attractive when the operation can be represented using the compact cumulative structure provided by the tree.

If you need more complicated range queries, range updates, or different forms of aggregation, a Segment Tree may provide a more suitable representation.

Fenwick Tree Mental Model

Instead of thinking of a Fenwick Tree as a traditional binary tree, think of it as an array of carefully selected partial sums. 

Original Array
      ↓
Store selected partial ranges
      ↓
Use the lowest set bit to navigate
      ↓
Combine partial ranges
      ↓
Answer prefix or range queries efficiently

Key Takeaways

  • A Fenwick Tree is also called a Binary Indexed Tree.
  • It is designed for efficient prefix-based aggregate queries and updates.
  • Fenwick Trees commonly use one-based indexing internally.
  • The lowest set bit is central to Fenwick Tree navigation.
  • Point updates take O(log n) time.
  • Prefix sum queries take O(log n) time.
  • Range sums can be calculated using two prefix sums.
  • A Fenwick Tree requires O(n) space.
  • It is generally simpler and more compact than a Segment Tree.
  • Segment Trees provide greater flexibility for more complex range operations.

Code Examples 

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(index, delta) {
    index += 1;

    while (index <= this.size) {
      this.tree[index] += delta;
      index += index & -index;
    }
  }

  prefixSum(index) {
    let sum = 0;
    index += 1;

    while (index > 0) {
      sum += this.tree[index];
      index -= index & -index;
    }

    return sum;
  }

  rangeSum(left, right) {
    if (left > right) {
      return 0;
    }

    return this.prefixSum(right) -
      (left > 0 ? this.prefixSum(left - 1) : 0);
  }
}

const values = [2, 4, 6, 8, 10, 12];
const bit = new FenwickTree(values.length);

for (let i = 0; i < values.length; i++) {
  bit.update(i, values[i]);
}

console.log(bit.prefixSum(4)); // 30
console.log(bit.rangeSum(1, 4)); // 28

// Add 4 to index 2: 6 → 10
bit.update(2, 4);

console.log(bit.rangeSum(1, 4)); // 32
    
class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(index, value) {
    index += 1;

    while (index <= this.size) {
      this.tree[index] += value;
      index += index & -index;
    }
  }

  prefixSum(index) {
    let result = 0;
    index += 1;

    while (index > 0) {
      result += this.tree[index];
      index -= index & -index;
    }

    return result;
  }
}

const frequencies = new FenwickTree(10);

frequencies.update(2, 1);
frequencies.update(2, 1);
frequencies.update(5, 1);
frequencies.update(7, 1);

console.log(frequencies.prefixSum(2)); // 2
console.log(frequencies.prefixSum(5)); // 3
console.log(frequencies.prefixSum(7)); // 4

Pro Tip

When you see repeated prefix-sum or range-sum queries mixed with point updates, consider a Fenwick Tree. The two expressions to remember are index += index & -index for updates and index -= index & -index for prefix queries.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.