gvikei's blog

Basic Binary Indexed Tree (English version)
By gvikei, 14 years ago, In English

Alright, so this is my 2nd post here. The 1st one, as you can see, was written in Vietnamese – my mother tounge, just because I thought that CodeForces Blog could be used  for my personal purposes and my entry would not be read by anyone else, except me :D

 

Due to that, I’m gonna translate that post into English so that anyone can read it and leave feedbacks :) One more thing to say, *I’m not the original author of this article, I just rewrite it to understand BIT better *

 

PS: As I said, Vietnamese is my mother tounge, and I’m only a high school student, so sorry for my bad English. J

 

Advantages of BIT:

            - Use less memory than RMQ

            - Easy to code

            - Can be used in many problems about number sequence

            - Runtime: O(logN)

 

Disadvantages : =’= BIT is hard to understand  (so that’s why I’m writing :D)

 

 

Main content:

            

BIT consists of two operations in an array A[1..N] of numbers

            SET (index, value) : To add value to A[index] (or A[index] += value)

            GET (index) :  To sum up A[1]..A[index ] (or Get ≔ A[1] + … + A[index])

 

          

Details:

            We know that a natural number can be expressed as a sum of the powers of 2, for example:

        

            Example 1:

                         22       =          16        +          4          +          2

                                    =          2^4      +          2^2      +          2 ^1

 

            Applying this idea for BIT, we’re going to express the sum of A[1]..A[n] as a sum of sub arrays, each of them has 2^k elements

 

How to code:

 

S(i,j) is the sum of A[i]..A[j]  (or S[i,j] = A[i] + A[i+1] +…+ A[j]). So with number 22 in Example 1, expressed as a sum of the powers of 2, is gonna be like this:

 

            S(1,22) = S(1,16) + S(17,20) + S(21,22)

To get the positions of sub arrays, use this formula:  i - i AND (-i) + 1.

Demo.:

            22 - (22 AND (-22)) = 20

            20 - (20 AND (-20)) = 16 

            16 - (16 AND (-16)) = 0

Thus, the structure of BIT T[] will be:

             T[i]: Sum of  S(i - i AND (-i) + 1 , i )

How does GET work?

 

Notice: GET (index) sums up A[1] → A[index].

 

Idea: To get the sum of A[1].. A[index], here we start with A[index] first. Parent of A[index] can be reached by using the following formula: i – i AND (-i)


Pseudo-code:

GET (T,i)

1 s ← 0

2 while i > 0 do

3          s ← s + T[i]

4          i ← i – i and (-i)

5 return s

 

How does SET work?

 

Notice: SET (index,value) adds value units to A[index]

Idea: To increase the value of A[index] with value, is to increase sub arrays which CONTAINS A[index]

Example : We want to add 1 to A[9]. So we also have to add 1 to sub arrays which contains A[9]. Look at the image, here we have A[10], A[12] and A[16] both consist of A[9] J

So how do we find which array contains A[9]?

Use this formula: i + i and (-i)! 

With this relationship, the demonstration of BIT will be opposed to the first one in GET procedure:


 Pseudo-code

 

SET (T,i,v)

1 while i ≤ size[T] do

2          T[i] ← T[i] + v

 3          i ← i + i AND (-i) 

So that's all I know about BIT  up to now :( I'ma continue with 2D BIT later. Thank you for reading.
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This data structure is also known as Fenwick tree. Point it out for better understanding what are you talking about.
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
"Fenwick tree" is a common name for post-soviet countries mainly. In other countries it is called Binary Indexed Tree.
→ Reply
  • 10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, a "binary indexed tree" is more general: exactly as the name says, its vertices (e.g. paths to them from the root) are, in some way, represented by the binary representation of their indices.

    For example, one version of segment trees is binary indexed as well, when the root has number 1 and vertex i has sons 2i and 2i + 1, so the path root — vertex i is given by the binary representation of i, starting from the most significant 1 and up to the least significant bit.

    A Fenwick tree just indexes the vertices in a special, compressed way.

    BTW, it's called Finnish tree in Slovakia, I think the name stems from some Finnish olympiad that it appeared in once :D

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could you post some problems (with the possibility to submit them) on this data structure? But not the ones which require to count sum of elements from i to j, some good ones.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    problems from acm.timus.ru where i used BIT: 1028,1090,1521,1523(something like 1028)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks a lot!
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Still cannot solve 1523. You say it is something like 1028, but 1028 is very easy - level[get(idx)]++; but 1523 does not look like this. Does it require K BITs?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        First of all, we have to find number of decreasing subsequences of len=K in the given permutation==> we can reverse permutation and find number of increasing subsequences=>answers will be the same. After that, construct array of pairs(x,y) - number ai and his index (in reversed permutation!) and sort them. Now your solution of 1028 problem is the answer for k=2 Inversions --> i mean your "get(idx)" - is the number of 2-inversions finishing in idx,so get(0)+get(1)+...+get(n) = number of 2-inversions. If you didn't understand it, draw points(sorted array of pairs - take first as the Y!! and second is the X!!) at the cartesian plane and will see the same features with 1028. after that repaat k-times 1028 solution. you need only one bit and two arrays - a_new,a_old. If you still have problems with understanding, i will send my code as private messgae to you
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I don't get to what you are applying 1028 solution k-times (what is a_new, a_old) - in 1028 I didn't store any frequencies, but was only updating the tree and levels. I think in order not to expand this blog endlessly, it would be better to simply send me your solution :) Thanks in advance!
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Test
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
BIT problems in SPOJ :

6256. INVCNT
6294. YODANESS (same as INVCNT but string)
8002. HORRIBLE (BIT or segment tree)
2815. INCSEQ (DP + BIT)
1329. KPMATRIX (DP + BIT)
1029. MATSUM (BIT 2D)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    How do you solve HORRIBLE using BIT?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      similar to segment tree solution.. save two element in BIT array.. first, multiplied number, second, not multiplied..

      when you want to update a..b += v , you can call update(a,v) and update(b+1,-v)
      and when you want to know sum a..b you can call query(b)-query(a-1)

      in query(p) function, you can do something like this :
      res += bit[i][0];
      res += bit[i][1]*(p-i);

      i think it's easier than segment tree.. :D
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes, please tell something more about this :) I'm very interested.
        → Reply
      • 11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have a doubt in the update(a,b,v).Suppose N=8 i.e there are total 8 elements. Now update(3,6,10) will update(add 10 to) elements from index 3 to index 6. As mentioned above update(3,6,10) can be performed as update(3,10) and update(7,-10). update(3,10) adds 10 to indexes 3,4 and 8. Similarly update(7,-10) adds -10 to indexes 7 and 8.Now to find sum(6) which is the sum of all elements from index 1 to 6 , will be sum(5...6)+sum(1.....4) but index 5 and 6 were not updated. So I want to ask how is it giving the correct result?

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
can someone please post a tutorial on implementing a 2D BIT ?
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have searched and found that the update and query in case of 2D binary Indexed trees are simple and the code snippets are provided but there is nowhere given on how to initialize the 2D Tree array in that case. Could you please help me in this.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I found this site http://zobayer.blogspot.in/

It explains 1D,2D BIT with simple example :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple yet nice explanation. Thanks a lot.

→ Reply