Fenwick Tree (BIT) — DSA

Fenwick Tree (Binary Indexed Tree)

A Fenwick Tree (also called a Binary Indexed Tree or BIT) is a data structure that efficiently answers prefix sum queries and supports point updates — both in O(log n) time and O(n) space.

It was introduced by Peter Fenwick in 1994 as a compact, cache-friendly alternative to segment trees for cumulative frequency tables.

The Problem It Solves

Suppose you have an array of numbers and need to repeatedly:

Update a single element (add a value at index i)
Query the prefix sum from index 1 to i

A naive array handles updates in O(1) but prefix queries in O(n). A prefix sum array handles queries in O(1) but updates in O(n). A Fenwick Tree gives you O(log n) for both.

Approach	Update	Prefix Query	Space
Plain array	O(1)	O(n)	O(n)
Prefix sum array	O(n)	O(1)	O(n)
Fenwick Tree (BIT)	O(log n)	O(log n)	O(n)
Segment Tree	O(log n)	O(log n)	O(4n)

The Core Idea: Responsibility Ranges

A Fenwick Tree stores partial sums, not individual values. Each index i in the BIT is responsible for summing a specific contiguous range of the original array.

The key insight is the lowbit trick: lowbit(i) = i & (-i). This extracts the lowest set bit of i, which determines how many elements index i is responsible for.

Text

Original array (1-indexed):
Index:  1    2    3    4    5    6    7    8
Value:  3    2    -1   6    5    4    -3   3

Binary representation:
  1 = 0001  →  lowbit = 1  →  responsible for 1 element
  2 = 0010  →  lowbit = 2  →  responsible for 2 elements
  3 = 0011  →  lowbit = 1  →  responsible for 1 element
  4 = 0100  →  lowbit = 4  →  responsible for 4 elements
  5 = 0101  →  lowbit = 1  →  responsible for 1 element
  6 = 0110  →  lowbit = 2  →  responsible for 2 elements
  7 = 0111  →  lowbit = 1  →  responsible for 1 element
  8 = 1000  →  lowbit = 8  →  responsible for 8 elements

BIT array (each cell stores a partial sum):
BIT[1] = arr[1]               = 3
BIT[2] = arr[1] + arr[2]      = 5
BIT[3] = arr[3]               = -1
BIT[4] = arr[1..4]            = 10
BIT[5] = arr[5]               = 5
BIT[6] = arr[5] + arr[6]      = 9
BIT[7] = arr[7]               = -3
BIT[8] = arr[1..8]            = 19

Visual tree structure (each node covers a range):
         [1..8]=19
        /
     [1..4]=10         [5..6]=9
    /                  /
 [1..2]=5  [3]=−1  [5]=5  [7]=−3
  /
[1]=3

The Lowbit Trick: i & (-i)

In two's complement, -i flips all bits of i and adds 1. The AND with the original i keeps only the lowest set bit — that's lowbit(i).

This single operation drives both traversals in the Fenwick Tree:

Query (prefix sum): subtract lowbit(i) to move to the parent — strips the lowest set bit, walking up toward index 0
Update: add lowbit(i) to move to the next responsible ancestor — sets the next higher bit, propagating the update upward

Text

Prefix sum query for index 6:
  i = 6 (0110)  →  sum += BIT[6]  →  i -= lowbit(6) = 2  →  i = 4
  i = 4 (0100)  →  sum += BIT[4]  →  i -= lowbit(4) = 4  →  i = 0
  STOP (i = 0)
  Result: BIT[6] + BIT[4] = 9 + 10 = 19  ← wait, that's sum(1..6)

Let's verify: 3+2+(-1)+6+5+4 = 19 ✓

Update at index 3 (add delta):
  i = 3 (0011)  →  BIT[3] += delta  →  i += lowbit(3) = 1  →  i = 4
  i = 4 (0100)  →  BIT[4] += delta  →  i += lowbit(4) = 4  →  i = 8
  i = 8 (1000)  →  BIT[8] += delta  →  i += lowbit(8) = 8  →  i = 16
  STOP (i > n)

Full JavaScript Implementation

class FenwickTree {
  constructor(n) {
    // 1-indexed: tree[0] is unused
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  // Add delta to index i (1-indexed)
  update(i, delta) {
    for (; i <= this.n; i += i & -i) {
      this.tree[i] += delta;
    }
  }

  // Prefix sum from index 1 to i (1-indexed)
  query(i) {
    let sum = 0;
    for (; i > 0; i -= i & -i) {
      sum += this.tree[i];
    }
    return sum;
  }

  // Range sum from index l to r (inclusive, 1-indexed)
  rangeQuery(l, r) {
    return this.query(r) - this.query(l - 1);
  }
}

// --- Build from existing array ---
function buildFenwick(arr) {
  const n = arr.length;
  const bit = new FenwickTree(n);
  for (let i = 0; i < n; i++) {
    bit.update(i + 1, arr[i]); // convert to 1-indexed
  }
  return bit;
}

// Alternatively: O(n) build (faster in practice)
function buildFenwickLinear(arr) {
  const n = arr.length;
  const bit = new FenwickTree(n);
  for (let i = 1; i <= n; i++) {
    bit.tree[i] += arr[i - 1];
    const parent = i + (i & -i);
    if (parent <= n) {
      bit.tree[parent] += bit.tree[i];
    }
  }
  return bit;
}

// --- Demo ---
const arr = [3, 2, -1, 6, 5, 4, -3, 3];
const bit = buildFenwick(arr);

console.log(bit.query(4));       // 10  (3+2+(-1)+6)
console.log(bit.query(6));       // 19  (3+2+(-1)+6+5+4)
console.log(bit.rangeQuery(3, 6)); // 14  ((-1)+6+5+4)

bit.update(3, 10); // arr[3] += 10  →  arr[3] is now 9
console.log(bit.rangeQuery(3, 6)); // 24  (9+6+5+4)

Point Query (Get the Actual Value)

Because the Fenwick Tree stores partial sums, getting the exact value at a single index requires a range query:

// Point query: get the current value at index i
FenwickTree.prototype.pointQuery = function(i) {
  return this.rangeQuery(i, i); // query(i) - query(i-1)
};

Note

The Fenwick Tree is 1-indexed by convention. If your data is 0-indexed, always add 1 before calling update/query.

Time and Space Complexity

Operation	Time	Notes
Build from array	O(n log n)	n individual updates
Build (linear)	O(n)	propagate directly in tree array
Point update	O(log n)	at most log₂(n) nodes updated
Prefix sum query	O(log n)	at most log₂(n) nodes visited
Range sum query	O(log n)	two prefix queries
Space	O(n)	one extra array of size n+1

Fenwick Tree vs Segment Tree

Both solve the same class of problems. Here is when to reach for each:

Aspect	Fenwick Tree	Segment Tree
Code length	~15 lines	~50–80 lines
Space	O(n)	O(4n)
Cache performance	Excellent (linear array)	Good (tree nodes)
Range updates + range queries	Requires BIT of BITs	Natural with lazy propagation
Non-invertible operations (max/min)	Not directly possible	Fully supported
Point update + prefix sum	Ideal	Works but overkill
Order statistics / rank queries	Supported	Supported

Tip

Default to a Fenwick Tree for prefix-sum problems — it is faster to write, uses less memory, and has better cache locality. Reach for a segment tree when you need range updates, lazy propagation, or non-invertible range operations like range-max.

Classic Interview Problem: Count Inversions

An inversion in an array is a pair (i, j) where i < j but arr[i] > arr[j]. Counting inversions in O(n log n) is a classic BIT application.

Approach: Process elements left to right. For each element x, the number of inversions it forms with previous elements equals the count of already-inserted values greater than x. We maintain a frequency BIT and query the suffix sum [x+1..MAX].

function countInversions(arr) {
  // Coordinate compress to range [1..n]
  const sorted = [...new Set(arr)].sort((a, b) => a - b);
  const rank = new Map(sorted.map((v, i) => [v, i + 1]));
  const n = sorted.length;

  const bit = new FenwickTree(n);
  let inversions = 0;

  for (const x of arr) {
    const r = rank.get(x);
    // Count of elements already inserted that are > x
    inversions += bit.query(n) - bit.query(r);
    bit.update(r, 1);
  }

  return inversions;
}

console.log(countInversions([3, 1, 2]));   // 2  → (3,1) and (3,2)
console.log(countInversions([5, 4, 3, 2, 1])); // 10

Classic Interview Problem: Range Sum with Updates

LeetCode 307 — Range Sum Query Mutable. Given an array, support two operations:

update(i, val): set arr[i] = val
sumRange(l, r): return sum of arr[l..r]

class NumArray {
  constructor(nums) {
    this.n = nums.length;
    this.nums = [...nums]; // keep original for "set" updates
    this.bit = new FenwickTree(this.n);
    for (let i = 0; i < this.n; i++) {
      this.bit.update(i + 1, nums[i]);
    }
  }

  // "set" semantics: update index i to val
  update(i, val) {
    const delta = val - this.nums[i];
    this.nums[i] = val;
    this.bit.update(i + 1, delta); // BIT is 1-indexed
  }

  sumRange(left, right) {
    return this.bit.rangeQuery(left + 1, right + 1); // 0→1 indexed
  }
}

const na = new NumArray([1, 3, 5]);
console.log(na.sumRange(0, 2)); // 9
na.update(1, 2);
console.log(na.sumRange(0, 2)); // 8

Order Statistics: K-th Smallest Element

A BIT over a frequency array lets you find the k-th smallest element in O(log² n) with binary search, or in O(log n) with a technique called binary lifting on the BIT.

// Find k-th smallest in O(log n) using binary lifting
// Requires values in range [1..n] (use coordinate compression first)
FenwickTree.prototype.kthSmallest = function(k) {
  let pos = 0;
  let logN = Math.floor(Math.log2(this.n));

  for (let pw = logN; pw >= 0; pw--) {
    const next = pos + (1 << pw);
    if (next <= this.n && this.tree[next] < k) {
      pos = next;
      k -= this.tree[next];
    }
  }
  return pos + 1; // 1-indexed position
};

// Example: track a multiset and find k-th element
const bit = new FenwickTree(10);
[3, 1, 4, 1, 5, 9, 2, 6].forEach(x => bit.update(x, 1));

console.log(bit.kthSmallest(1)); // 1  (smallest)
console.log(bit.kthSmallest(3)); // 2  (3rd smallest: 1, 1, 2)
console.log(bit.kthSmallest(5)); // 4  (5th: 1,1,2,3,4)

2D Fenwick Tree

The BIT generalizes cleanly to two dimensions for 2D prefix sum queries with updates. Each index (i, j) is responsible for a rectangle of cells, driven by lowbit in each dimension.

Operations:

update(r, c, delta): add delta to cell (r, c)
query(r, c): sum of rectangle (1,1) to (r,c)
rangeQuery(r1,c1,r2,c2): sum of sub-rectangle using inclusion-exclusion

class FenwickTree2D {
  constructor(rows, cols) {
    this.rows = rows;
    this.cols = cols;
    this.tree = Array.from({ length: rows + 1 }, () =>
      new Array(cols + 1).fill(0)
    );
  }

  update(r, c, delta) {
    for (let i = r; i <= this.rows; i += i & -i) {
      for (let j = c; j <= this.cols; j += j & -j) {
        this.tree[i][j] += delta;
      }
    }
  }

  // Prefix sum: (1,1) to (r,c)
  query(r, c) {
    let sum = 0;
    for (let i = r; i > 0; i -= i & -i) {
      for (let j = c; j > 0; j -= j & -j) {
        sum += this.tree[i][j];
      }
    }
    return sum;
  }

  // Sum of rectangle (r1,c1) to (r2,c2) — inclusion-exclusion
  rangeQuery(r1, c1, r2, c2) {
    return (
      this.query(r2, c2) -
      this.query(r1 - 1, c2) -
      this.query(r2, c1 - 1) +
      this.query(r1 - 1, c1 - 1)
    );
  }
}

const grid = new FenwickTree2D(4, 4);
grid.update(1, 1, 3);
grid.update(2, 3, 5);
grid.update(3, 2, 7);

console.log(grid.query(3, 3));           // 15 (3+5+7)
console.log(grid.rangeQuery(2, 2, 3, 3)); // 12 (5+7)

Text

2D Prefix Query Inclusion-Exclusion:

  (1,1)────────────────(1,c2)
    │                    │
    │   A  │      B      │
    │──────(r1-1,c1-1)───│
    │      │             │
    │   C  │      D      │
    │      │             │
  (r2,1)──────────────(r2,c2)

  sum(D) = query(r2,c2) - query(r1-1,c2) - query(r2,c1-1) + query(r1-1,c1-1)
           ──────────── ─ ───────────────  ─ ───────────── + ─────────────────
           A+B+C+D      ─  A+B             ─  A+C           + A

Note

The 2D Fenwick Tree has O(log R × log C) per update and query, and uses O(R × C) space — suitable for grids up to about 1000×1000.

BIT with Range Updates

By default a BIT supports point updates and prefix queries. With a second BIT, you can support range updates and point queries, or even range updates and range queries.

The trick is the identity: if you add delta to every element in [l, r], the prefix sum at index i changes by a formula that can be split across two BITs.

// Range update, range query using two BITs
// Derived from the identity:
//   prefix_sum(i) = B1[i] * i - B2[i]
// where B1 and B2 are auxiliary BITs
class RangeBIT {
  constructor(n) {
    this.n = n;
    this.b1 = new FenwickTree(n);
    this.b2 = new FenwickTree(n);
  }

  // Add delta to all elements in [l, r]
  rangeUpdate(l, r, delta) {
    this.b1.update(l, delta);
    this.b1.update(r + 1, -delta);
    this.b2.update(l, delta * (l - 1));
    this.b2.update(r + 1, -delta * r);
  }

  // Prefix sum [1..i]
  prefixSum(i) {
    return this.b1.query(i) * i - this.b2.query(i);
  }

  // Range sum [l..r]
  rangeSum(l, r) {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }
}

const rbit = new RangeBIT(6);
// arr = [0,0,0,0,0,0] initially
rbit.rangeUpdate(2, 5, 3); // add 3 to positions 2-5
rbit.rangeUpdate(1, 3, 2); // add 2 to positions 1-3

// arr is now [2, 5, 5, 3, 3, 0]
console.log(rbit.rangeSum(1, 6)); // 18
console.log(rbit.rangeSum(2, 4)); // 13  (5+5+3)

Common Pitfalls

Warning

Fenwick Trees are 1-indexed. Passing index 0 to update() causes an infinite loop because `0 & -0 = 0`, so `i` never advances. Always add 1 when bridging from 0-indexed arrays.

Off-by-one on range queries: rangeQuery(l, r) = query(r) - query(l-1). Using query(l) instead of query(l-1) includes the element at l twice
Overflow in large sums: use BigInt or ensure your accumulator type can hold n × maxValue
Coordinate compression required when values are large (e.g. up to 10⁹) — map them to [1..n] before using a frequency BIT
2D BIT memory: a 10⁵ × 10⁵ grid is impossible; use coordinate compression or an offline approach
Non-invertible operations: BIT cannot support range-max/min queries because subtraction of partial results is meaningless — use a segment tree

Interview Cheat Sheet

Problem pattern	BIT technique
Count inversions	Frequency BIT + suffix query
Range sum query + point update	Standard BIT
Range update + point query	Difference BIT (single BIT)
Range update + range query	Two BITs (b1, b2)
K-th smallest in dynamic set	Frequency BIT + binary lifting
2D rectangle sum + point update	2D BIT
Count elements in range [a,b]	Frequency BIT: query(b) - query(a-1)

Tip

In a competitive programming contest, the entire Fenwick Tree fits in about 10 lines. Memorize the three-line update loop and three-line query loop — they are the only things that differ between a BIT and a plain array.

Complete Self-Contained Example

// ─── Fenwick Tree ────────────────────────────────────────────────
class BIT {
  constructor(n) { this.t = new Array(n + 1).fill(0); this.n = n; }
  update(i, d) { for (; i <= this.n; i += i & -i) this.t[i] += d; }
  query(i)     { let s = 0; for (; i > 0; i -= i & -i) s += this.t[i]; return s; }
  range(l, r)  { return this.query(r) - this.query(l - 1); }
}

// ─── Problem: Given queries on array [1,3,5,7,9,11] ──────────────
const arr = [1, 3, 5, 7, 9, 11];
const n   = arr.length;
const bit = new BIT(n);
arr.forEach((v, i) => bit.update(i + 1, v));

console.log('Sum [1..6]:', bit.query(6));     // 36
console.log('Sum [2..4]:', bit.range(2, 4));  // 15  (3+5+7)

// Update: set index 3 (0-based) → index 4 (1-based) to 100
const idx = 4; // 1-indexed
const delta = 100 - arr[idx - 1];
arr[idx - 1] = 100;
bit.update(idx, delta);

console.log('After update, Sum [1..6]:', bit.query(6)); // 129
console.log('After update, Sum [3..5]:', bit.range(3, 5)); // 116 (5+100+9)

Sum [1..6]: 36
Sum [2..4]: 15
After update, Sum [1..6]: 129
After update, Sum [3..5]: 116