What is a Binary Indexed Tree (BIT)?

A BIT or Fenwick Tree is a data structure that can efficiently update elements and calculate prefix sums in O(log n) time using binary index logic.

Fenwick vs Segment Tree?

Fenwick Trees are easier to implement and use less space (O(n)). However, they primarily handle prefix sums and invertible operations.

How does (i & -i) work?

This bit manipulation trick isolates the least significant bit (LSB), which determines the range of elements covered by a specific index in the tree.

Fenwick Tree (Binary Indexed Tree)

A data structure that provides efficient methods for calculation and manipulation of the prefix sums of a table of values.

Original:

BIT Array:

Ready to build Fenwick Tree

Update:

Sum:

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

Every integer can be represented as a sum of powers of 2 (binary representation). Similarly, a prefix sum can be represented as a sum of non-overlapping sub-ranges. Fenwick Tree cleverly arranges these ranges so that both updates and prefix sum queries take O(log N) time.

Concept

A Fenwick Tree (or Binary Indexed Tree) is an array-based data structure. Each index i stores the sum of a range defined by the least significant bit (LSB) of i.

How it Works

Storage: BIT[i] stores the sum of the range [i - (i&-i) + 1, i].
Update(i, delta): Add delta to BIT[i], then move to i + (i & -i) (next range covering i).
Query(i): Add BIT[i] to sum, then move to i - (i & -i) (parent range).

Step-by-Step Breakdown

Update(index, val):

1. Add val to current node.
2. Move to parent: index += index & (-index).
3. Repeat until index exceeds array size.

Query(index):

1. Add current node value to sum.
2. Move to child/predecessor: index -= index & (-index).
3. Repeat until index becomes 0.

When to Use

Need Prefix Sums with frequent updates.
Counting inversions in an array.
Less memory overhead than Segment Tree (O(N) vs O(4N)).

When NOT to Use

Range Minimum/Maximum Query (possible but complex).
Complex range updates (lazy propagation is harder than Segment Tree).

How to Identify

Problems involving "Prefix Sums" and "Mutable Arrays". Often used in competitive programming for simpler range query tasks.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep