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. Pingback: Range updates with BIT / Fenwick Tree | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s