Binary Indexed Tree
7 problems · 6 with full explanations
1 Easy2 Medium3 Hard
A Fenwick tree (BIT) answers prefix-sum queries and point updates in O(log n) with O(n) space - simpler to implement than a segment tree. Index arithmetic uses i += i & (-i) to traverse. Use for inversion counting, order statistics, and frequency prefix sums.
How to practice
To practice Binary Indexed Tree problems effectively, start with the Easy problems listed below, trace through each solution on paper, then re-implement without looking. When you can recognise the binary indexed tree pattern within 30 seconds of reading a new problem, move on to Medium difficulty. Use the related topic pages and our study guide for a structured progression.
Start here (Easy + explained)
All Binary Indexed Tree problems
- 2179.Count Good Triplets in an ArrayUnknown
- 2913.Subarrays Distinct Element Sum of Squares IEasy
- 2916.Subarrays Distinct Element Sum of Squares IIHard
- 3505.Minimum Operations to Make Elements Within K Subarrays EqualHard
- 3737.Count Subarrays With Majority Element IMedium
- 3739.Count Subarrays With Majority Element IIMedium
- 3841.Palindromic Path Queries in a TreeHard