(Viết lại từ bài của tác giả paulmcvn chỉ với mục đích cá nhân)
- 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)
Vietnamese
and 'hỉu' not in Vietnamese Dictionary
На этих летних сборах на последнем шуточном туре было шесть простых-простых задач с одним "но": они были написаны на языках, отличных от русского и английского =) Это, на самом деле, очень весело - разбираться во всяких вьетнамских языках...
А (i - (i & (-i))) это красиво.
Мне больше нравятся формулы
+= x & -xи-= x & -xNói tiếng việt cũng phải nói có văn hóa chứ ._.