Advanced Trees

Fenwick Tree (BIT)

What is a Fenwick Tree?

A Fenwick Tree (also called a Binary Indexed Tree, or BIT) solves the same core problem a Segment Tree does — prefix/range sums with fast point updates — but with a much smaller footprint: one plain array, no explicit tree nodes or pointers at all. The "tree" is implicit, encoded entirely in the binary representation of each index.

How Does the Implicit Structure Work?

Every index i in the BIT array is responsible for a range of the original array whose length is exactly the value of i's lowest set bit (its "lowbit"). Index 6 in binary is 110, whose lowest set bit is 2, so BIT[6] covers a range of 2 elements. Index 8 is 1000, whose lowest set bit is 8, so BIT[8] covers all 8 elements up to it. This single bit trick is the entire structure — no recursion, no children pointers, just index arithmetic.

Each BIT index's responsibility range, sized by its lowest set bit
12345678

Moving between indices uses that same lowbit value: adding it to an index walks up toward larger ranges (used when propagating a point update to every range that includes it), and subtracting it walks down toward smaller ranges (used when accumulating a prefix sum). Both walks take exactly O(log n) steps, because each step clears or sets one more bit in the index.

Fenwick Tree vs. Segment Tree

The tradeoff for this smaller footprint is flexibility: a Fenwick Tree's range query only works by combining prefix sums (range[l,r] = prefix(r) - prefix(l-1)), which requires the underlying operation to have an inverse. That works great for sum, but not for operations like minimum or maximum, which don't have an inverse — a Segment Tree is needed for those instead.

Algorithm Steps

  1. Build: start with an all-zero BIT array, then apply a point update for every element of the input array
  2. Point Update(index, delta) — add delta to the element at index:
    • Convert to 1-indexed: i = index + 1
    • While i is within bounds: add delta to BIT[i], then move to the next responsible index with i += lowbit(i)
  3. Prefix Sum(index) — sum of everything from 0 to index:
    • Convert to 1-indexed: i = index + 1
    • While i > 0: add BIT[i] to the running total, then move down with i -= lowbit(i)
  4. Range Sum(l, r) = Prefix Sum(r) - Prefix Sum(l - 1)

Time Complexity

  • Build: O(n log n) naively (n point updates), or O(n) with a direct construction trick.
  • Point Update: O(log n) — one walk upward through responsible ranges.
  • Prefix/Range Query: O(log n) — one walk downward accumulating partial sums.

Time Complexity Analysis

Advertisement
Daily DSA Challenge by Scale Engineer

Build a Fenwick tree (Binary Indexed Tree), then update a value or query a range

No Fenwick tree yet — build one over a random array
No Fenwick tree yet — build one over a random array
BIT nodeUpdate pathPrefix sum path (added)Subtracted prefix (for range queries)

Test Your Knowledge before moving forward!

Fenwick Tree Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Fenwick Tree Implementation

// Fenwick Tree (Binary Indexed Tree) for prefix/range sums
class FenwickTree {
  constructor(size) {
    this.n = size;
    this.bit = new Array(size + 1).fill(0); // 1-indexed
  }

  static fromArray(arr) {
    const tree = new FenwickTree(arr.length);
    arr.forEach((value, index) => tree.update(index, value));
    return tree;
  }

  // Add 'delta' to the element at 0-indexed 'index'
  update(index, delta) {
    let i = index + 1; // convert to 1-indexed
    while (i <= this.n) {
      this.bit[i] += delta;
      i += i & -i; // move to the next range that includes this index
    }
  }

  // Sum of elements from 0 to index (inclusive), 0-indexed
  prefixSum(index) {
    let i = index + 1;
    let sum = 0;
    while (i > 0) {
      sum += this.bit[i];
      i -= i & -i; // move down to the next chunk of the prefix
    }
    return sum;
  }

  // Sum of elements from l to r (inclusive), 0-indexed
  rangeSum(l, r) {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

// Usage example
const tree = FenwickTree.fromArray([2, 5, 1, 4, 9, 3]);
tree.rangeSum(1, 3);   // 5 + 1 + 4 = 10
tree.update(2, 9);     // add 9 to index 2 (was 1, becomes 10)
tree.rangeSum(1, 3);   // 5 + 10 + 4 = 19

Done With the Learning

Mark Fenwick Tree (BIT) as done and view it on your dashboard

Explore Other Tree Topics

Segment Tree

B-Tree

Trie (Prefix Tree)

Red-Black Tree

AVL Balancing