All Roadmaps›🧠 Data Structures & Algorithms›Phase 4›Binary Indexed Tree (Fenwick Tree)

Binary Indexed Tree (Fenwick Tree)

0/12 in this phase0/57 across the roadmap

📖 Concept

A Binary Indexed Tree (BIT) / Fenwick Tree provides O(log n) prefix sum queries and point updates, like a simpler alternative to segment trees for sum-based problems.

Key operations:

  • prefix_sum(i): sum of arr[0..i] → O(log n)
  • update(i, delta): add delta to arr[i] → O(log n)
  • range_sum(l, r): prefix_sum(r) - prefix_sum(l-1) → O(log n)

How it works (the magic of lowbit):

  • lowbit(x) = x & (-x) gives the lowest set bit
  • Each index i is responsible for a range determined by lowbit(i)
  • Index i stores the sum of lowbit(i) elements ending at i
  • Query: walk "up" by removing lowbit
  • Update: walk "up" by adding lowbit

BIT vs Segment Tree:

Feature BIT Segment Tree
Code complexity Simple Complex
Space O(n) O(4n)
Range query Sum only Sum, min, max, etc.
Range update With trick Lazy propagation
Constant factor Very fast Somewhat slower

🏠 Real-world analogy: Think of BIT like a cascading summary system. Each node covers a range of elements, but the ranges are cleverly sized so that any prefix sum can be computed by adding at most O(log n) nodes.

💻 Code Example

codeTap to expand ⛶
1// BINARY INDEXED TREE (Fenwick Tree)
2class BIT {
3  constructor(n) {
4    this.n = n;
5    this.tree = new Array(n + 1).fill(0); // 1-indexed
6  }
7

8  // Add delta to index i (1-indexed)
9  update(i, delta) {
10    while (i <= this.n) {
11      this.tree[i] += delta;
12      i += i & (-i); // Add lowbit
13    }
14  }
15

16  // Prefix sum [1..i]
17  query(i) {
18    let sum = 0;
19    while (i > 0) {
20      sum += this.tree[i];
21      i -= i & (-i); // Remove lowbit
22    }
23    return sum;
24  }
25

26  // Range sum [l..r] (1-indexed)
27  rangeQuery(l, r) {
28    return this.query(r) - this.query(l - 1);
29  }
30

31  // Build from array
32  static fromArray(arr) {
33    const bit = new BIT(arr.length);
34    for (let i = 0; i < arr.length; i++) {
35      bit.update(i + 1, arr[i]); // 1-indexed
36    }
37    return bit;
38  }
39}
40

41// USAGE
42const bit = BIT.fromArray([1, 3, 5, 7, 9, 11]);
43console.log(bit.query(3));       // 9 (1 + 3 + 5)
44console.log(bit.rangeQuery(2, 4)); // 15 (3 + 5 + 7)
45bit.update(3, 5);                // arr[3] += 5 → [1, 3, 10, 7, 9, 11]
46console.log(bit.rangeQuery(2, 4)); // 20 (3 + 10 + 7)
47

48// COUNT INVERSIONS using BIT — O(n log n)
49function countInversions(arr) {
50  const sorted = [...new Set(arr)].sort((a, b) => a - b);
51  const rank = new Map();
52  sorted.forEach((v, i) => rank.set(v, i + 1));
53

54  const bit = new BIT(sorted.length);
55  let inversions = 0;
56

57  for (let i = arr.length - 1; i >= 0; i--) {
58    inversions += bit.query(rank.get(arr[i]) - 1);
59    bit.update(rank.get(arr[i]), 1);
60  }
61  return inversions;
62}
63

64// 2D BIT — for matrix range sum queries
65class BIT2D {
66  constructor(m, n) {
67    this.m = m; this.n = n;
68    this.tree = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
69  }
70  update(r, c, delta) {
71    for (let i = r; i <= this.m; i += i & (-i))
72      for (let j = c; j <= this.n; j += j & (-j))
73        this.tree[i][j] += delta;
74  }
75  query(r, c) {
76    let sum = 0;
77    for (let i = r; i > 0; i -= i & (-i))
78      for (let j = c; j > 0; j -= j & (-j))
79        sum += this.tree[i][j];
80    return sum;
81  }
82}

🏋️ Practice Exercise

Practice Problems:

  1. Implement a BIT with update and prefix sum query
  2. Range sum query using BIT
  3. Count inversions in an array using BIT
  4. Find the number of elements less than k in a subarray
  5. Count smaller elements after self
  6. Range update, point query using BIT
  7. 2D BIT for matrix prefix sums
  8. Find kth smallest element using BIT + binary search
  9. Count of range sum (how many subarrays have sum in [lo, hi])
  10. Reverse pairs using BIT

⚠️ Common Mistakes

  • BIT is 1-indexed — index 0 is unused; common source of off-by-one errors

  • BIT only supports prefix operations efficiently — range operations need subtraction trick

  • BIT cannot do range min/max — only additive operations (sum, count); use segment tree for min/max

  • Forgetting to coordinate-compress before using BIT for inversion counting — values may be too large

  • Not understanding lowbit(x) = x & (-x) — this is the fundamental building block

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Binary Indexed Tree (Fenwick Tree)

← PreviousSegment Trees — Range Queries & UpdatesNext →Balanced BSTs (AVL, Red-Black — Conceptual)