 # BIT / Fenwick Tree data structure C++ implementation

A BIT (Binary Indexed Tree) or Fenwick Tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values.

It supports the following operations :

1. SUM(1…b): Cumulative sum of elements in the range [1…b]
2. SUM(a…b): Cumulative sum of elements in the range [a…b]
3. UPDATE(k, v): Update kth element by an amount v ( v can be +ve or -ve)
4. SCALE_UP(c): Multiply all elements by an amount c
5. SCALE_DOWN(c): Divide all elements by an amount c

Space Complexity: O(N) for N elements

Time Complexity: O(log N) for SUM and UPDATE and O(N) for SCALE, where N is the number of elements

For a complete tutorial on BIT, view the topcoder tutorial.

Take a look at the C++ implementation.

Continue to Range Updates with BIT

## 5 thoughts on “BIT / Fenwick Tree data structure C++ implementation”

1. Joe Blo says:

Your title need to add the word “Binary Tree” It’s not a General Tree. It’s binary.

• kartik kukreja says:

The title is BIT, short for Binary Indexed Tree.

2. Akash says:

can solve this problem http://www.spoj.com/problems/GSS4/ using binary index tree. I can’t come up with a solution

• kartik kukreja says:

It’s not that hard to solve this problem with BIT. The trick is that there’s only so many times you can take square root of a number, followed by rounding down to nearest integer, before it reduces to 1. Once it reduces to 1, any further operations are useless. So, if we keep track of which numbers are not 1, we can solve this problem.

Found this implementation: https://github.com/mariosal/algo/blob/master/spoj/gss4.cc