gvikei's blog

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By gvikei, 14 years ago, In English
(Viết lại từ bài của tác giả paulmcvn chỉ với mục đích cá nhân)

Ưu điểm:
- Bộ nhớ thấp
- Cài đặt đơn giản
- Có thể giải được nhiều bài toán về dãy số
- Thời gian chạy: O(logN)

Khuyết điểm : ==' Khó hỉu vl



Nội dung chính:
Gồm 2 thao tác trên dãy số: A[1..N]
SET (index, value) : Tăng phần tử A[index] lên value đơn vị
GET (index) : Tính tổng đoạn con A[1..index]


Chi tiết:
Do các số tự nhiên có thể được biểu diễn dưới dạng tổng các luỹ thừa của 2, ví dụ:
VD1:
 22 = 16 + 4 + 2
= 2^4 2^2 2 ^1

Áp dụng ý tưởng này cho cây nhị phân, ta sẽ biểu diễn tổng A[1..i] dưới dạng các tổng các đoạn con có số phần tử là luỹ thừa của 2.


Ý tưởng cài đặt:

Gọi S(i,j) là tổng các phần tử của A[i..j] hay S(i,j) = A[i] + A[i+1]... A[j]. Áp dụng với VD1 việc biểu diễn dưới dạng tổng các luỹ thừa của 2 ta được: 

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

Để thu được vị trí các đoạn con, ta làm như sau : i - (i AND (-i)). Demo:
22 - (22 AND (-22)) = 20
20 - (20 AND (-20)) = 16 
16 - (16 AND (-16)) = 0

Như vậy, cấu trúc cây nhị phân T[] sẽ là:
 T[i] lưu tổng S((i - i AND (-i)) + 1 , i )


(CÒN TIẾP)

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it