fenwick tree - OpenGenus IQ: Learn Computer Science

Count inversions in an array using Fenwick Tree

Fenwick tree is usually used for range query problems but it can be used to solve the problem of finding the number of inversions in an array efficiently.

Data Structures

Understanding Fenwick tree (Binary Indexed Tree) with Range product

Fenwick tree is a tree based data structure that is widely used to solve range query problems in logarithmic time O(log N) which would otherwise have taken linear time O(N). In this article, we have explained it in depth using the range product query problem.

Data Structures

2D Fenwick Tree / 2D Binary Indexed Tree

Fenwick Tree is used to answer range or interval queries in an array in logarithmic time. Fenwick tree can be generalized to multiple dimensions. 2D Fenwick tree is one such implementation used to answer sub-matrix queries, i.e. queries in 2 dimensions. It requires the operation to be invertible.

Data Structures

Fenwick Tree (Binary Indexed Tree)

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 is that it can be only used with an operation that is invertible.