Fenwick Tree (Binary Indexed Tree)


(Team) #1

Fenwick Tree / Binary indexed tree (BIT) is a data structure used to process interval/range based queries. Compared to segment tree data structure, Fenwick tree uses less space and is simpler to implement.
One disadvantage of Fenwick tree is that it can be only used with an operation that is invertible. For example, Addition is an invertible operation: if a + b = c then c - a = b (where - acts as inverse of addition) Maximum is a non-invertible operation: given max(a, b) = c We don't have any inverse operation to get back a or b.

Read this article to understand Fenwick Tree/ Binary Indexed Tree in depth

Have a doubt or thought? Join the discussion now

This is a companion discussion topic for the original entry at http://iq.opengenus.org/fenwick-tree-binary-indexed-tree/