Fenwick Tree (BIT)
Visualize how a Binary Indexed Tree enables efficient prefix sums and point updates.
Free theory articleVisualize 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.