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 :

**SUM(1…b): **Cumulative sum of elements in the range [1…b]
**SUM(a…b):** Cumulative sum of elements in the range [a…b]
**UPDATE(k, v)**: Update k^{th} element by an amount v ( v can be +ve or -ve)
**SCALE_UP(c):** Multiply all elements by an amount c
**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…

28.635308
77.224960

### Like this:

Like Loading...

*Related*

Pingback: Range updates with BIT / Fenwick Tree | Everything Under The Sun

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

The title is BIT, short for Binary Indexed Tree.

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

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