Chuyên đề Cấu trúc dữ liệu đặc biệt

ễn Minh Hiếu 
•Nếu Y1 >= CF hoặc Y2 Y2 này hoàn toàn chẳng phủ gì lên 
đoạn CS -> CF cả -> Ta không phải xét tới các nút con của nó nữa.
•Nếu đoạn [Y1,Y2] ∩ [CS,CF] ≠ ∅ thì ta sẽ gọi tới các nút con của nó, xét tiếp các nút 
con của nó với đoạn Y1,Y2 này.
Chương trình minh hoạ :
Procedure Dong(Y1 , Y2 , P , S , F : Integer ) ;
Var
 mid : Integer ;
Begin
 If (Y1 >= C[F])or(Y2 <= C[S]) then Exit ; 
 If (Y1 <= C[S] )and(C[F] <= Y2) then Begin
 SoHCNphu[P] := SoHCNphu[P] – 1 ;
 If SoHCNphu[P] > 0 then Exit ; 
 BiPhu[P] := BiPhu[ P*2 ] + BiPhu[P*2+1] ; 
 Exit ;
 End ;
 If S + 1 >= Fn then Begin { Tức là P là nút lá }
 Biphu[P] := 0 ; 
 Exit ; 
 End ;
 mid := (S+F) div 2 ;
 Dong( Y1 , Y2 , P*2 , S , mid ) ;
 Dong( Y1 , Y2 , P*2+1 , mid ,F ) ;
 If SoHCNphu[P] = 0 then Biphu[P] := Biphu[P*2] + Biphu[P*2+1] ;
End ;
Như vậy Biphu[1] cho ta biết tới khe L này thì tung độ từ C1 -> C2*N đã bị phủ là bao 
nhiêu , diện tích bị phủ khe L = Độ rộng * Biphu[1] . Sau đây là chương trình mô tả 
đoạn này :
Procedure Solve ;
Var
 Dientich , Rong , i : LongInt ;
Begin
 Dientich := 0 ;
 Mo( A[1].Y1 , A[1].Y2 , 1 , 1 , N ) ;
 For i := 2 to 2*n do Begin
 Rong := A[i].x – A[i-1].x ;
 Dientich := Dientich + Rong * BiPhu[1] ;
 If A[i].Y1 < A[i].Y2 then Mo( A[i].Y1 , A[i].Y2 , 1 , 1 , N ) 
 Else Dong( A[i].Y2 , A[i].Y1 , 1 , 1 , N ) ;
 End;
End ;
Ta có thể khẳng định thuật toán này là hoàn toàn đúng đắn bởi khi ta xét tới 1 điểm Đóng 
i thì chắc chắn tồn tại 1 điểm Mở j đã xuất hiện trước đó , và 2 điểm i và j này là đại diện 
cho 1 HCN R , HCN R này có hoành độ bắt đầu từ điểm j và kết thúc ở điểm i, nên 
chừng nào chưa xét tới điểm i thì HCN R này vẫn tồn tại , vẫn phủ lên 1 số đoạn nào đó 
 Trang 4
Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu 
của tung độ. Mỗi khi ta gặp 1 điểm Mở tức là gặp 1 HCN có cạnh bên trái có hoành độ = 
điểm đang xét , và khi gặp một điểm Đóng tức là 1 HCN đã bị loại khỏi vùng đang xét và 
sẽ không được xét tới sau này nữa.
Như vậy bài toán đã được giải quyết. Với mỗi lân cập nhật đỉnh i vào cây nhị phân ta mất 
logN bước, có tất cả 2*N đỉnh -> cấp độ thuật toán O(2*NlogN), đúng như đã nói ở trên 
ở đây ta chỉ xét mỗi HCN thông qua 2 điểm , mỗi điểm đúng 1 lần.
Ý nghĩa cây nhị phân : Như vậy ta có thể thấy mỗi nút P của cây nhị phân đại diện cho 
một đoạn , mà giá trị của nó = tổng giá trị của các đoạn con . Bởi vậy nó giúp ta không 
phải truy xuất tới tất cả những nút mà chỉ thông qua một số nút cha mà thôi. ( Ví dụ ở đây 
là Y1 <= C[S] , C[F] <= Y2 , tức là đã phủ lên cả đoạn rồi , không phải xét các đoạn con 
làm gì nữa )
Interval Tree : Cây nhị phân mà ta sử dụng trong bài tập nói trên chính là Interval Tree. 
Vậy khái quát lại thì Interval Tree là gì ? Đó là một cây nhị phân mà mỗi nút đại diện cho 
một “đoạn “ hay một dãy các phần tử liên tiếp có chung một tính chất nào đó và các nút 
con của nó đại diện cho một đoạn nhỏ hơn. Khi ta muốn đếm , liệt kê xem một đoạn cho 
trước có bao nhiêu phần tử thoả mãn một tính chất X ( biểu diễn trên máy tính được , 
thông thường chỉ là quan hệ > hoặc <) cho trước, thì khi xét tính chất này trên một nút 
của cây nhị phân thì xảy ra 3 tình huống :
Cả đoạn đều thoả mãn tính chất này , khi đó số phần tử thoả mãn trong đoạn đó = số 
phần tử của đoạn.
Cả đoạn đều không thoả mãn tính chất -> số phần tử thoả mãn trong đoạn đó = 0.
Có một số phần tử thoả mãn và các phần tử này nằm liên tiếp nhau trong đoạn đang xét. 
Khi đó ta sẽ lại phải kiểm tra với 2 nút con của nó. Nút con trái = nửa đoạn bên trái , nút 
con phải = nửa đoạn bên phải.
Khi muốn cập nhật thêm phần tử hay giảm vào đoạn ta cũng làm như vậy . Về mặt dung 
lượng bộ nhớ thì Internval Tree cần 2*N phần tử ( = số nút của cây ) nhưng có thể có 
nhiều trường hợp bị suy biến nên tốt nhất nên để 4-> 8*N .
Tuy nhiên nói thì là như vậy nhưng ta cũng cần làm nhiều bài tập mới có thể nắm rõ , sử 
dụng thuần thục nó được.
II . Binary Index Tree : 
Binary Index Tree cũng là một mô hình cây và nó cũng không khác Interval Tree 
về mục đích sử dụng , lấy dữ liệu được cập nhật từ nút con… . Về nguyên tắc thì bất cứ 
bài nào giải được bằng Binary Index Tree cũng đều đưa về Interval Tree được nhưng 
chưa chắc đã có chiều ngược lại ( theo ý kiến chủ quan của mình ) . Thuật toán cũng chỉ 
có cấp độ O(NlogN) nhưng tốt hơn ở chỗ là nó không cần lưu tất cả 2*N nút mà chỉ lưu 
N nút mà thôi.Sau đây là mô hình của cây Binary Index Tree :
 Trang 5
Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu 
Mỗi nút X ở đây đại diện cho các cho nút X và các nút con của X. Rõ ràng ta thấy mô 
hình của nó khác hẳn so với mô hình của cây nhị phân . Sau đây là mô tả chi tiết đồ thị :
+ Nếu đồ thị chỉ có 1 nút -> không có cung nào cả. 
+ Nếu nút i lẻ , nó sẽ có cung nối với nút i+1 ( là nút chẵn ) .
+ Không xét các đỉnh lẻ nữa , các đỉnh chẵn còn lại sẽ được đánh số lại ( ngầm định 
trong đầu thôi ), số thứ i = i shr 1 . Quay lại bước 1.
Trong Binary Index Tree , để biết được nút i có cha là nút nào người ta sử dụng công 
thức đã được CM như sau : 
 Cha(i) = i + i and ( i xor ( i-1) ) ;
Mỗi khi cập nhật một phần tử ở có giá trị tương ứng là X ta sẽ tăng số phần tử = X lên: 
A[x] := A[x] + 1 và gửi thông báo lên cho cha của nó , cha của nó lại tiếp tuc gửi lên cho 
tới khi nào > N thì thôi. Mỗi lần gửi thông báo , ta lại tăng số phần tử của cha nó lên , tức 
là A[cha] := A[cha] + 1 . Như vậy cũng có nghĩa là A[x] của ta lưư lại số phần tử có giá 
trị x và số phần tử của các con của nó.
Và để kiểm tra xem từ 1 -> X có bao nhiêu phần tử người ta sử dụng một cách thức đệ 
quy rất thông minh như sau :
 Số phần tử 1 -> X = Số phần tử lưu được ở nút X 
+ Số phần tử 1 -> ( X – X and ( X xor ( X-1) ) ) .
Ví dụ mhư muốn biết có bao nhiêu phần tử ở <= 11 chẳng hạn :
Số phần tử = A[11] + Số phần tử( 1 => 11 – 11 and (11 xor 10) ) .
 = A[11] + Số phần tử( 1 => 10 ) .
 = A[11] + A[10] + Số phần tử (1 => 8) ;
 = A[11] + A[10] + A[8] + Số phần tử ( 1 => 0) = A[11] + A[10] + A[8]. ( hoàn 
toàn chính xác , nhìn vào hình vẽ ).
 Trang 6
1 5 7
3
9 11
2 6
14
4
12
8
10
13 15
16
Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu 
Cấp độ của Binary Index Tree đã được CM rằng luôn luôn nhỏ hơn O(NlogN) , bởi vậy 
chương trình chạy rất nhanh , hơn nữa lại còn nhanh hơn rất nhiều so với dùng Interval 
Tree, bộ nhớ sử dụng cũng ít hơn . 
B. Bài tập ứng dụng : 
Bài 1 : Electronic Auction ( Đấu giá lợn sắt )
Có một sự thiếu hụt lợn sắt ở một đất nước nọ. Bởi vậy lợn sắt được bán đấu giá. 
Chúng được bán ở các phiên đấu giá điện tử . Khách hàng khi đến mua có quyền đặt giá 
của mình . Họ sẽ thông báo cho ban quản lý giá của mình sẵn sàng đưa ra để mua về một 
con lợn sắt ( số tiền này nằm trong khoảng 0.01 VND -> 10000.00 VND và luôn có chính 
xác 2 chữ số sau dấu phẩy, tức là không bao giờ có chuyện khách hàng đặt giá là 0.211 
hay 3.412 mà chỉ có thể là 0.21 hoặc 3.41 mà thôi ). Hết lần này tới lần khác những 
người bán sẽ đưa ra K con lợn để đấu giá , và mỗi con lợn sẽ được bán cho K người đầu 
tiên trả giá >= X. Nếu như không có đủ K người thì số lợn còn lại sẽ bị chuyển tới nước 
khác ngay lập tức , và không được bán tiếp trên đất nước này nữa .
Khách hàng cũng có thể thông báo huỷ bỏ cái giá mà mình đã đưa ra . Sau mỗi 
cuộc giao dịch , khách hàng vẫn tiếp tục mua bán tiếp với cái giá mà họ đã thông báo cho 
tới khi nào họ thông báo huỷ bỏ giá mà mình đưa ra thì thôi. Mỗi con lợn sắt được bán thì 
ban quản lý đấu giá được nhận hoa hồng là 0.01 VND. Hãy tính xem sau khi kết thúc tất 
cả các cuộc giao dịch thì ban quản lý lãi bao nhiêu tiền.
Giới hạn : 
Freepascal : + Số dòng trong file Input <= 100000 dòng.
 + Time limit 0.5 s , bộ nhớ 5000 KB.
Turbo Pascal:+ Số dòng trong file Input <= 60000 dòng. Giá tiền giảm xuống <= 300.
 + Time limit 0.5 s , bộ nhớ 200KB .
INPUT
Gồm nhiều dòng , mỗi dòng có thể có dạng 1 trong 3 trường hợp sau :
"BID X " : Cho biết vừa có thêm 1 người thông báo giá của mình là X VND.
"DEL X" : Cho biết vừa có 1 người thông báo huỷ cái giá X mà mình đã đưa ra.
"SALE X K" : Cho biết có một người bán vừa quyết định dem bán K con lợn sắt với 
cái giá ít nhất cho mỗi con lợn là X VND. K người đầu tiên trả giá >= X sẽ được mua 
mỗi người 1 con.
Dòng cuối cùng ghi 1 từ duy nhất "QUIT" thông báo đã kết thúc tất cả các phiên giao 
dịch, các cuộc mua bán đều đã kết thúc .
OUTPUT
1 số thực duy nhất ( cũng ghi chính xác 2 chữ số sau dấu phẩy ) là lãi mà ban quản lý thu 
được .
Ví dụ :
Input Output
BID 0.01
BID 10000
BID 5000
0.06
 Trang 7
Chuyên đề cấu trúc dữ liệu đặc biệt Nguyễn Minh Hiếu 
BID 5000
SALE 7000 3
DEL 5000
SALE 3000 3
SALE 0.01 3
QUIT
Giải thích : 
- 4 dòng đầu tiên cho biết có 4 người đã đưa ra giá của mình, đó là các giá 0.01 , 10000 , 
5000 , 5000.
- Dòng thứ 5 cho biết có một người đã đem bán 3 con lợn mỗi con giá tối thiểu là 7000 
VND.->Chỉ có 1 người mua là người đặt mức giá 10000, còn lại 2 con lợn sẽ bị chuyển 
đi, không bán nữa -> Lãi 0.01 đồng.
- Dòng thứ 6 cho biết có một người đã huỷ bỏ cái giá 5000 VND mà anh ta đưa ra. Tức là 
lúc này chỉ còn lại 3 người với 3 mức giá 0.01 , 10000 , 5000 VND.
- Dòng thứ 7 cho biết có một người đã đem bán 3 con lợn mỗi con giá tối thiểu là 3000 
VND.->Chỉ có 2 người mua là người đặt mức giá 10000 và 5000, còn lại 1 con lợn sẽ bị 
chuyển đi, không bán nữa -> Lãi 0.02 đồng.
- Dòng thứ 8 cho biết có một người đã đem bán 3 con lợn mỗi con giá tối thiểu là 0.01 
VND.->Có 3 người mua là người đặt mức giá 10000 ,0.01 và 5000-> Lãi 0.03 đồng.
- Dòng 9 Cho biết các phiên giao dịch đã kết thúc .
- Vậy tổng lãi sẽ là 0.01 + 0.02 + 0.03 = 0.06 VND.
Thuật giải : Đây là một bài điển hình cho việc sử dụng Binary Index Tree, nếu biết sử 
dụng khéo thì cũng có thể sử dụng Interval Tree được.
 Trang 8