fenwick tree - OpenGenus IQ: Computing Expertise & Legacy

Booking Concert Tickets in Groups [using BIT and Segment Tree]

In this article, we have solved the problem of Booking Concert Tickets in Groups. This involve the concept of Binary Indexed Tree and Segment Tree.

Algorithms

Find the longest increasing subsequence using Fenwick Tree

You are given an array of length N. You have to find the longest increasing subsequence from the given array. We will try to solve this problem using Fenwick Tree which will take O(N logN) time complexity.

Data Structures

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.