Binary Indexed Tree (Fenwick)

Range Update, Point Query

Use a difference array inside the BIT. To add delta to range [L,R]: update(L, +delta) and update(R+1, −delta). To get the value at index i: query prefix sum up to i. Clever dual of the standard BIT.

O(log n) per op

O(n)

How It Works

Range update with point query inverts the standard BIT by storing a difference array inside it. To add delta to every element in [L, R], perform just two point updates on the differences: update(L, +delta) and update(R+1, -delta). The value of element i is then the prefix sum of differences up to i — a single standard BIT query — because every range whose L <= i < R+1 contributes its delta exactly once and cancels beyond R.

Both operations stay O(log n) with the identical ten-line BIT code; only the interpretation of what is stored changes. Compared with a lazy segment tree it is dramatically simpler, at the cost of generality: only invertible, additive updates work. Extending the idea with a second BIT tracking i*delta terms yields full range-update range-sum in O(log n), still lighter-weight than lazy propagation for pure addition workloads.

Step-by-Step Visualization

Range update BIT: add delta to range [L,R]

OperationrangeUpdate(1, 3, +5)

1/3

Code

Java

class RangeBIT {
  BIT bit;

  RangeBIT(int n) { bit = new BIT(n); }

  void rangeUpdate(int l, int r, int delta) {
    bit.update(l, delta);
    bit.update(r + 1, -delta);
  }

  int pointQuery(int i) {
    return bit.query(i);
  }
}

Tips & Gotchas

1Use a difference array inside the BIT

2Range update [L,R] += delta: update(L, +delta), update(R+1, -delta)

3Point query at i: just query prefix sum up to i

Practice Problems

1Corporate Flight Bookings
2Range Addition
3Car Pooling

About the Binary Indexed Tree (Fenwick) Pattern

A simpler alternative to segment trees for prefix sum queries. Uses bit manipulation on indices to determine parent-child relationships. Much less code than a segment tree, but limited to prefix-based operations.

Key insight

If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.

Common Range Structures Interview Problems

Range Sum Query - Mutable
Count of Smaller Numbers After Self
Range Minimum Query
Longest Increasing Subsequence (BIT approach)

Frequently Asked Questions

Why do two point updates suffice to update an entire range?

The BIT holds differences, and a prefix sum reconstructs actual values. Adding delta at L makes every prefix sum from L onward include it, and subtracting delta at R+1 cancels it for positions past R — so exactly the positions in [L, R] see the change, regardless of range length.

How do I also support range-sum queries under range updates?

Use two BITs: with the algebraic identity for summing a difference array, prefix_sum(i) = query1(i)*i - query2(i), where BIT1 stores deltas and BIT2 stores delta*(position-1) terms. Both range update and range sum remain O(log n), covering the same ground as an additive lazy segment tree.

When does this trick break down, forcing a segment tree?

It relies on updates being additive and invertible so differences reconstruct values. Range assignment (set all of [L, R] to x), range min/max updates, or non-commutative composed operations cannot be expressed as differences, and those workloads need lazy propagation on a segment tree.