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 Fenwick tree (binary indexed tree) is a data structure for efficiently calculating and updating the prefix sums of a table of values.

1-BASED INDEXING

READY

Values

Each slot holds the total of a run of values whose length is its own lowest set bit. Query a prefix to watch that low bit get dropped.

Values

Sum first

Add at

Delta

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.

Sample Problems

Range Sum Query - Mutable

Can be solved with BIT or Segment Tree.

Count of Smaller Numbers After Self

Classic application of BIT.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Segment Tree

Red-Black Tree