Fenwick Tree
AlgorithmsMediumCompute prefix sums using LSB bitwise operations and point updates.
Alt+Shift+F
Configuration Panel
Binary Indexed Tree Forest
Double-click empty canvas to create root, select node to add child or delete.
Source Array:
[0]3
[1]2
[2]-1
[3]6
[4]5
[5]4
[6]-3
Time Complexity
O(log N) query & update
Auxiliary Space Complexity
O(N) BIT storage array
Conceptual Overview
A Fenwick Tree (Binary Indexed Tree / BIT) is a data structure that can efficiently update elements and calculate prefix sums in an array of numbers in logarithmic time.
Algorithm Mechanism
Each index in a Fenwick Tree stores the sum of a range of elements determined by its Least Significant Bit (LSB). Point updates run in O(log N) by hopping parents ($i \mathrel{+}= i \mathbin{\&} -i$), and prefix queries run in O(log N) by hopping children ($i \mathrel{-}= i \mathbin{\&} -i$).
Source: CP-Algorithms reference guide