gvikei's blog

By gvikei, 10 years ago, ,

Alright, so this is my 2 nd post here. The 1 st 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

- 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)

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)

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.

• 0

 10 years ago, # |   0 This data structure is also known as Fenwick tree. Point it out for better understanding what are you talking about.
 10 years ago, # |   +1 "Fenwick tree" is a common name for post-soviet countries mainly. In other countries it is called Binary Indexed Tree.
•  7 years ago, # ^ |   0 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
 10 years ago, # |   0 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.
•  10 years ago, # ^ |   0
•  10 years ago, # ^ |   0 problems from acm.timus.ru where i used BIT: 1028,1090,1521,1523(something like 1028)
•  10 years ago, # ^ |   0 Thanks a lot!
•  10 years ago, # ^ |   0 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?
•  10 years ago, # ^ |   0 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
•  10 years ago, # ^ |   0 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!
•  10 years ago, # ^ |   0 sent
 10 years ago, # |   0 Test
 9 years ago, # |   +1 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)
•  9 years ago, # ^ |   0 How do you solve HORRIBLE using BIT?
•  9 years ago, # ^ |   0 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
•  9 years ago, # ^ |   0 Can you please be more clear on maintaining 2D array part, how to update? Thank you
 » 7 years ago, # |   0 can someone please post a tutorial on implementing a 2D BIT ?