What is a Fenwick Tree?

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that allows efficient querying and updating of cumulative sums of elements in an array.

It was invented by Peter Fenwick in 1994 and is commonly used in computational geometry, graph algorithms, and other applications where prefix sums and range queries are required.

The Fenwick Tree has a space complexity of O(n) and can perform both queries and updates in O(log n) time complexity.

Basic Properties

• Low-level indexing: A Fenwick Tree is indexed starting from 1, rather than 0 like an array.
• Cumulative sums: Each node in the Fenwick Tree stores the cumulative sum of a range of elements.
• Prefix sum: The cumulative sum from the start of the array to a given index can be calculated efficiently using the Fenwick Tree.

1// Fenwick Tree code here

xxxxxxxxxx

#include <iostream>

​

int main() {

  // Fenwick Tree code here

  return 0;

}