Fenwick Trees

Things we will discuss,
  • Need for Fenwick Trees
  • Basic Operation in a Fenwick Tree
  • Implementation in C++
  • Explanation of the code
  • Applications of Fenwick Trees
  • Practice Problems
Need for Fenwick Trees

Consider the problem of updating an array and finding cumulative sum for a number of queries.Time complexity of each of these operations will be O(n) for finding sum (we can have another array which stores the sum of first i elements) and O(1) for updating for each query.These operations can be done in O(log n) time for each query using Fenwick Tree or Binary Indexed Tree(BIT).

Basic Operation in a Fenwick Tree

Fenwick Tree is based on the idea that every number can be represented as a power of 2.So the indices that are a power of two,have the sum of values in indices up to that power of two and other numbers can be represented using this.
Operations for constructing a Fenwick Tree:
getSum():Get the cumulative frequency till that index
Update:Update the value at given index.
Below is an explanatory video of the algorithm.

Implementation in C++

Explanation of the code

Application of Fenwick Trees

  • Fenwick tree can be used to implement arithmetic coding algorithm
  • It can also be used to find inversions in an array.
  • Other operations like updating over a range and querying over a range is also possible using Fenwick Trees
  • Note that Binary Indexed tree can be used only if the operation performed is associative.
Practice Problems
  1. Suffixes and Prefixes (SPOJ)
  2. Mega Inversions (SPOJ)
  3. Spread (CodeChef)
  4. Party Row House (HackerEarth)
  5. Operations and Tree (HackerEarth)

Any doubt related to the above content can be mentioned in the comment section.

Thank You