Binary Indexed Tree | Fenwick Tree

A Fenwick tree or binary indexed tree is a data structure that was first used for data compression. It is often used for storing frequencies and manipulating cumulative frequency tables.

Lets take a following problem to understand Binary Indexed Tree.

There are n shelves in a library and possible query may be:

1. Add book in ith shelf.

2. Sum total number of books from jth shelf to kth shelf.

A[] contain no. of books in ith shelf.


A[] = [5] [1] [8] [11] [52] [28] [0]

       1   2   3     4    5    6   7

Naive solution has following Time complexity for above query:

Query 1 : O(1)

Query 2 : O(n) , as in worst case(for cumulative frequency of nth element) we have to traverse whole array.

For example : cumulative frequency of 5th element is = A[1] + A[2] + A[3] + A[4] + A[5] ~ O(n)

Using Binary Index tree we can reduce down Time complexity from O(n) to O(logn).

Concept behind Binary Indexed Tree:

Lets consider frequency of 7 different element


Frequency table :  [5] [1]  [8]  [11] [52] [28]  [0]

Cumulative table : [5] [6]  [14] [25] [77] [105] [105]

                    1   2   3     4    5    6     7

Using above representation of Frequency table we can change frequency in O(1) time. Like If we want to increment frequency of 3rd element by 7 i.e from 8 to 15 then for cumulative frequency we have to add all element before 3rd element, which is pretty slow if take a large n.

After increment 3rd element by 7 frequency table and cumulative table become:


Frequency table :  [5] [1]  [15]  [11] [52] [28]  [0]

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence? If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

Basic Idea is like Each integer can be represented as sum of powers of two. In the same way, cumulative frequency can be represented as sum of sets of subfrequencies.

One way to visualize this is to change the representation from being an array to being a binary tree of nodes. Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node. For example, suppose we construct the following binary tree from these nodes:


             4

          /     \

         2       6

        / \     / \

       1   3   5   7

Now, we can represent each node by storing the cumulative sum of all the values including that node and its left sub-tree. For example,

value at node 4 would contain sum of its left tree’s nodes i.e [node1] + [node2] + [node3] + [node4] = 5 + 1 + 15 + 11 = 32

similarly, for node 5 there is no child so its value would be same its value i.e 52


Before:

[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]

  1     2     3     4     5     6     7

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

After:

                 4

               [+32]

              /     \

           2           6

         [ +6]       [+80]

         /   \       /   \

        1     3     5     7

      [ +5] [+15] [+52] [ +0]

Determine the cumulative sum
Given above tree structure, it’s easy to determine the cumulative sum of any index.

Lets see how:

1. First write each index in its binary notation like this:


                100(4)

                [+32]

              /      \

         010(2)       110(6)

        [+6]           [+80]

        /   \          /   \

     001(1)  011(3) 101(5) 111(7)

      [+5] [+15]    [+52]   [+0]

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

2. Here, Take all binary numbers one by one and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it. You are now left with the following:


              (empty)(4)

               [+32]

              /     \

           0(2)      1(6)

         [+6]        [+80]

         /   \       /   \

     00(1)   01(3) 10(5)  11(7)

      [+5] [+15]   [+52] [ +0]

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

3. Treat 0 means “left” and 1 means “right”

4. If we want to look up cumulative frequency of ith index then take its bit number and then move from root to that element in downwards direction using that bit pattern. During this look up we will just care about right links.

For Example :

A) Look up of 5:

Bit number of 5 is 10 ,so path is RIGHT–>LEFT ;

i) Start from element(4) –move right—>(6) | sum = 32

ii) Element(6)–move LEFT–>Element(5) | sum = sum + 0 , as we have move left so we are ignoring 80

iii) We are at our target element(5) , so add 52 to sum | sum = sum + 52

so cumulative sum of element(5) is 84

during this we have traverse only equal to height of binary tree, So time complexity would be O(logn).

B) Look up of 3:

Bit number of 3 is 01 , so path is LEFT–>RIGHT ;

i) Start from element(4) –move LEFT–>(2) | sum = 0, as we moved left , so we are ignoring 32

ii) Element(2)–>move RIGHT–>(3) | sum = sum + 6, add current element value to sum

iii) Found target element(3) , so add 15 to sum | sum = sum + 15

So cumulative sum of element(3) become 21

Update or increment the frequency of any element


              (empty)(4)

               [+32]

              /     \

           0(2)      1(6)

         [+6]        [+80]

         /   \       /   \

     00(1)   01(3) 10(5)  11(7)

      [+5]  [+15]  [+52]   [ +0]

Given the above tree structure it is easy to update/increment frequency of any element.
1. Treat 0 means “left” and 1 means “right”

2. If we want to update frequency of ith index then take its bit number and then move from root to that element in downwards direction using that bit pattern. During this look up we will just care about left links.

For example:

A) Update frequency of  1st index by 5 :

Bit number of 1 is 00 ,so path is LEFT–>LEFT ;

i) Start from root element i.e 4 and add 5 to this node. i.e 32+5 = 37

ii) Move to left direction i.e to element(2) and add 5 to this element. i.e 6 + 5 = 11

iii) Then again move to left direction i.e to target element and add 5 to this element too. 5+5 = 10

So resultant tree become:


              (empty)(4)

               [+37]

              /     \

           0(2)      1(6)

         [+11]        [+80]

         /   \       /   \

     00(1)   01(3) 10(5)  11(7)

     [+10]   [+15] [+52]   [+0]

 

during this we have traverse only equal to height of binary tree, So time complexity would be O(logn).

How to isolate last non-zero digit

Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b.
Now, we can easily isolate the last digit, using bitwise operator AND with num and -num

       a 1b
&      a¯1b
--------------------
= (0...0)1(0...0)

In the next post will see implementation part to see How to Update and Look up cumulative frequency.

Site Footer