Explore modules

Fenwick Tree (BIT)

Visualize how a Binary Indexed Tree enables efficient prefix sums and point updates.

Free theory article

Visualize how a Binary Indexed Tree enables efficient prefix sums and point updates.

Concept & interpretation

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. Unlike a standard array where prefix sums take O(n) time or updates on a precalculated prefix sum array take O(n) time, a Fenwick Tree achieves both operations in O(log n) time.

Read the full free theory article