What is a Fenwick Tree (Binary Indexed Tree)?

Difficulty: 6/10

prefix sum, point update, logarithmic time

Fenwick Tree

A Fenwick Tree, or Binary Indexed Tree, is a compact structure for maintaining prefix aggregates and supporting point updates efficiently. It uses the binary representation of indices to store partial sums. For an array of n elements, point updates and prefix-sum queries both take O(log n), while memory usage is O(n).

javascript

1
Point update: O(log n).
2
Prefix query: O(log n).
3
Range sum: O(log n) using two prefix queries.
4
Space: O(n).
5
Simpler and often more memory-efficient than a Segment Tree for suitable operations.
6
It is primarily suited to operations with an invertible prefix aggregation such as sum.

Scenario Questions

0-2 years experience

Follow-up Questions