gvikei's blog

Cây chỉ số nhị phân (Binary Indexed Tree)
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)
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
It's all is interesting, but i can't read it. In what language it was written?
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
The language is Vietnamese. In this entry , the author said she copied from another one for her own individual purposes.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
'Khó hỉu vl', sorry but the team 'vl' not in Vietnamese :))
→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nói tiếng việt cũng phải nói có văn hóa chứ ._.

→ Reply