HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
HIỆU QUẢ SỬ DỤNG CẤU TRÚC INTERVAL TREE
I.Đặt vấn đề
Các bài toán trên dãy số đang xuất hiện nhiều trong các đề thi olympic tin học quốc gia và quốc
tế, Có rất nhiều cấu trúc lưu trữ được sử dụng để xử lý đối với các bài toán dạng này, Theo tìm
hiểu cá nhân tôi thì một trong các cấu trúc lưu trữ hiệu quả với các thao tác xử lý ít tốn thời gian
hơn các cấu trúc khác đó là INTERVAL TREE (Cây đoạn).
Cây đoạn là một công cụ rất hữu dụng được sử dụng nhiều trong các bài toán trên dãy số, hoặc
được quy về các bài toán xử lý trên dãy số, đặc biệt là các bài toán có nhiều công việc cần xử lí và
nhiều truy vấn xen kẻ nhau.
Chính vì vậy, Tôi viết chuyên đề này nhằm làm rõ mức độ hiệu quả khi sử dụng cấu trúc interval
tree thông qua một số bài tập có thể áp dụng cấu trúc này để giải quyết.
II.Nội dung
1.Lý thuyết nền tảng
Cây phân đoạn là một cây, các nút của nó lưu thông tin của một đoạn xác định. Interval tree là
một cây nhị phân mà mỗi nút không phải là lá đều có đúng 2 nút con. Nếu nút A lưu thông tin của
đoạn từ i..j thì 2 nút con của nó, A1 và A2 lần lượt lưu thông tin của các đoạn i..m và m+1..j, với
m=(i+j) div 2 là phần tử giữa của đoạn.
Vì đầy là cây nhị phân, lại có đầy đủ 2 nút con, để đơn giản thì ta có thể biễu diễn cây chỉ bằng 1
mảng 1 chiều với ý nghĩa như sau:
Nút 1 là nút gốc, nút k( nếu không phải là nút lá) thì có 2 con là các nút k*2 ( nút con trái) và
k*2+1(nút con phải).
Nút 1 sẽ lưu thông tin của đoạn 1..n ( với n là độ dài của dãy số).
Vậy nút 2 sẽ lưu thông tin đoạn 1.. (n+1) div 2 và nút 3 sẽ lưu thông tin đoạn (n+1)div 2 +1 ..n.
Tương tự theo định nghĩa thì ta có thể biết được nút thứ k sẽ lưu thông tin của một đoạn xác định
nào đó. Sau đây là hình ảnh 1 cây INTERVAL TREE với n =7:
1
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Có một vấn đề là với 1 đoạn n phần tử thì mảng biễu diễn cây sẽ có bao nhiêu phẩn tử là đủ,
người ta đã chứng minh được cây interval tree chỉ cần tối đa là 4*n-5 phần tử, vì vậy khi khai báo
1 cây interval tree ta thường khai báo 1 mảng 1..4*n.
Trên interval tree có 2 thao tác cần xử lý: 1 là cập nhật thay đổi cho đoạn i..j và 2 là lấy thông tin
cần có của đoạn i..j, những mỗi nút của interval trê chỉ lưu những đoạn xác định, vì vậy 2 thao tác
này có thể cần tác động đến nhiều nút.
Để dễ hình dung, ta lấy 1 ví dụ cụ thể:
Cho 1 dãy n phần tử (n<= 10^5), ban đầu mỗi phần tử có giá 0. Có q<=10^5 truy vấn, mỗi truy
vấn là 1 trong 2 thao tác sau: 1 là gán giá trị v(v>0) cho phần tử ở vị trí i, 2 là tìm giá trị lớn nhất
trong đoạn i..j bất kì.
Cách đơn giản nhất là ta có 1 mảng A[1..100000], với thao tác 1 thì gán A[i]=v, thao tác 2 thì cho
1 vòng for từ i đến j để tìm max, nhưng cách này trong trường hợp có nhiều truy vấn thứ thì sẽ
chạy rất lâu, trừng hợp xấu nhất là n*q. Dễ thấy cách này không thể chạy trong thời gian cho
phép.
Cách dùng interval như sau:
Với truy vấn 1, ta sẽ cập nhật là kết quả max cho tất cả các đoạn mà chứa phần tử thứ i,
những đoạn còn lại thì không làm gì cả vì không ảnh hưởng đến.
Với đoạn truy vấn 2, ta cần tìm kết quả max trong số tất cả những đoạn nằm gọn tron i..j,
tức là những đoạn có điểm đầu >=i và điểm cuối <=j.
Gọi T[1..400000] of longint là mảng để lưu trữ cây interval tree. T[i] là giá trị lớn nhất
trong đoạn mà nút k lưu giữ thông tin.
Khi gặp truy vấn 1, ta làm như trong thủ tục sau:
2
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Procedure truyvan1(k,l,r,i:longint);
Var m: longint;
Begin
1. if (l<=i) or (r>i) then exit;
2.
if (l=r) then
begin
T[k]:= v; exit;
end;
3. m:=(l+r) div 2;
4. truyvan1(k*2,l,m,i);
5. truyvan1(k*2+1,m+1,r,i);
6. T[k]:=max(T[k*2],T[k*2+1]);
end;
Ta sẽ phân tích thủ tục truyvan1:
- Thủ tục này có các tham số k,l,r,i với ý nghĩa: l và r là điểm đầu và điểm cuối của đoạn mà nút k
lưu trữ thông tin, i chính là phần tử cần gán giá trị v.
- Trong thủ tục có 1 biến m để xác định phần tử nằm giữa đoạn l..r.
- Câu lệnh 1 có ý nghĩa là ta sẽ bỏ qua không làm gì với các đoạn không chứa phần tử thứ i (l>i
hoặc r T[k]:=max(T[k*2],T[k*2+1])
Khi gọi thủ tục truy vấn 1, ta sẽ gọi từ nút gốc, tức là gọi truyvan1(l,l,n,i);
Vậy là đã xong yêu cầu thứ nhất, nhưng cái ta cần để xem chương trình có hoạt động tốt hay
không lại là kết quả của yêu cầu thứ 2, vì vậy thủ tục truyvan1 là để giúp thủ tục truyvan2 sau đây
để tìm được kết quả với đoạn i..j bất kì,
3
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Procedure truyvan2(k,l,r,i,j:longint);
Var m: longint
Begin
1. if (l>j) or (r= r) then
Begin
res:=max(res,T[k]);exit;
End;
3. m:=(l+r) div 2;
4. truyvan2(k*2,l,m,I,j);
5. truyvan2(k*2+1,m+1,r,i,j);
end;
Phân tích: Thủ tục truy vấn 2 này có các tham số với ý nghĩa như thủ tục 1, có thêm số j vì cần lấy
kết quả trên đoạn i..j.
Mỗi đoạn l..r sẽ có 3 khả năng với đoạn i..j.
a: l..r không giao i..j, trường hợp này bỏ qua không làm gì cả( câu lệnh 1).
b: l..r nằm gọn trong i..j, trường hợp này thì ta chỉ cần tối ưu kết quả khi so sánh với T[k] vì: Ta
đã xác định được phần tử lớn nhất trong đoạn l..r nhờ thử tục 1, và do l..r nằm gọn trong i..j nên
không cần đi vào 2 nút con của nó (câu lệnh 2).
c: l..r không nằm trong đoạn i..j nhưng có 1 phần giao với i..j, trường hợp này thì ta sẽ đi vào 2
nút con của nó để lấy kết quả, đến khi nào gặp phải 2 trường hợp đầu ( câu lệnh 4 và 5).
Suy nghĩ kĩ sẽ thấy thủ tục truy vấn 2 không bỏ sót cũng như tính thừa phần tử nào ngoài đoạn i..j.
Khi gọi thủ tục truyvan2 ta cũng gọi từ nút gốc truyvan2(l,l,n,i,j). Sau thủ tục thì in ra res là kết
quả cần tìm.
Người ta cũng chứng minh được rằng, độ phức tạp của mỗi thủ tục truyvan1 và truyvan2 không
quá log(n). Vì vậy thuật toán dùng interval tree cho bài toán này có độ phức tạp không quá
q*log(n)=10^5*log(10^5). Có thể chạy trong thời gian cho phép.
Đây là 1 trong những ví dụ cơ bản nhất về interval tree, hi vọng các bạn đã có thể hiểu và cài đặt
nó. Trong khi nghiên cứu về các bài tập sau đây, ta sẽ tìm hiểu 1 vài kiểu sử dụng interval tree
khác.
Đây cũng là 1 trong những cấu trúc dữ liệu thường găp được sử dụng trong các kì thi Olympic Tin
học trên thế giới. Các bài tập này sẽ được trình bày trong phần bài tập ứng dụng.
4
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
2.Bài tập ứng dụng
Bài toán 1: Dãy con tăng dài nhất
Cho dãy số a1 , a2 ,..., an . Hãy tìm dãy con (không nhất thiết gồm các phần tử liên tiếp) tăng dài
nhất.
Đây là bài toán qui hoạch động quen thuộc: Đặt f[i] là độ dài dãy con tăng dài nhất kết thúc tại ai.
Ta có công thức qui hoạch động sau:
f [i] max {f [k ]: k i, ak ai } 1
(1)
Có nhiều cách để tính toán (1) trong thời gian O(log n). Một trong những cách như vậy là sử dụng
tìm kiếm nhị phân. Ở đây, chúng ta tiếp cận theo một cách khác:
Trước tiên giả thiết rằng ai 1,2,..., n với i=1,2,...,n. Bất đẳng thức ak ai có thể viết dưới dạng
ak [1... ai 1] . Do đó việc tính (1) có thể qui về việc tính lần lượt f[1], f[2], .... và với mỗi
i=1,2,...,n thì f[i] được tính bằng cách lấy giá trị lớn nhất của các giá trị f đã được tính có điểm
cuối thuộc [1...ai-1] (mỗi lần có được giá trị f[i] ta ghi nhận nó vào vị trí ai[1...n]) và ta có thể sử
dụng IT để thực hiện các truy vấn tìm max này). Dưới đây là mã chương trình viết bằng IT:
void update(int r,int k,int l,int u,int v,int val) {
if (vl) return;
if (u<=k && l<=v) {dt[r]+=val; return;}
int g=(k+l)/2;
dt[2*r]+=dt[r]; dt[2*r+1]+=dt[r]; dt[r]=0;
update(2*r,k,g,u,v,val);
update(2*r+1,g+1,l,u,v,val);
it[r]=max(it[2*r]+dt[2*r],it[2*r+1]+dt[2*r+1]);
}
5
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
int get(int r,int k,int u,int v) {
if (vl) return -INF; // INF là giá trị đủ lớn
if (u<=k && l<=v) return it[r]+dt[r];
int g=(k+l)/2;
dt[2*r]+=dt[r]; dt[2*r+1]+=dt[r]; dt[r]=0;
int t1=get(2*r,k,g,u,v);
int t2=get(2*r+1,g+1,l,u,v);
it[r]=max(it[2*r]+dt[2*r],it[2*r+1]+dt[2*r+1]);
return max(t1,t2);
}
for(int i=1;i<=n;i++) {
f[i]=get(1,1,n,1,a[i]-1)+1;
update(1,1,n,a[i],a[i],f[i]);
}
Độ phức tạp là O(n log n)
Tuy nhiên, để có thể sử dụng IT như trên chúng ta đã phải giả thiết rằng ai [1... n] . Nếu như
không có điều kiện trên thì sao? Trong trường hợp này chúng ta phải sử dụng một kỹ thuật thường
được gọi là rời rạc hóa: Cho tương ứng dãy a1 , a2 ,..., an với dãy b1 , b2 ,..., bn sao cho thỏa mãn:
Nếu ai a j , ai a j , ai a j thì bi bj , bi bj , bi bj
bi [1...n]
6
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Dễ thấy việc tìm dãy con tăng dài nhất trên dãy a1 , a2 ,..., an hoàn toàn giống như việc tìm dãy con
tăng dài nhất trên dãy b1 , b2 ,..., bn . Đoạn mã dưới đây làm công việc này:
for(int i=1;i<=n;i++) x[i]=a[i];
sort(x+1,x+n+1);
for(int i=1;i<=n;i++) b[i]=lower_bound(x+1,x+n+1,a[i])-x;
Nếu code bằng Pascal, trước tiên ta sắp xếp lại mảng A theo chỉ số:a[id[1]] ≤a[id[2]]≤...a[id[n]].
Sau đó thực hiện đoạn mã sau:
m=1; b[id[1]]:=1;
for i:=2 to n do
begin
if a[id[i]]>a[id[i-1]] then inc(m);
b[id[i]]:=m;
end;
Tất nhiên, cách tiếp cận trên để giải bài toán 1 phức tạp hơn cách tiếp cận sử dụng tìm kiếm nhị
phân truyền thống. Tuy vậy qua ví dụ trên có thể tổng kết một số điều khi sử dụng IT:
Nói chung, IT được xây dựng trên miền giá trị của mảng. Luôn co miền giá trị vào một
khoảng hữu hạn đủ nhỏ [1...m] bằng kỹ thuật rời rạc hóa (nếu cần thiết)
Viết các biểu thức so sánh thành các biểu thức tập hợp: a x b được viết thành
x [a, b] để xây dựng được các truy vấn max, min, sum trên một khoảng. Điều này là
quan trọng vì nó thể hiện đặc trưng của IT.
Bài tập 2: Tính diện tích hình chữ nhật phủ
Cho N hình chữ nhật có tọa độ nguyên nằm trên mặt phẳng tọa độ và có các cạnh song song
với các trục. Mỗi hình chữ nhật được cho bởi tọa độ đỉnh trái trên và đỉnh phải dưới.
Yêu cầu: Hãy tính diện tích mà tất cả các hình chữ nhật này phủ lên.
Input: COVER.INP
Dòng đầu là số N – số hình chữ nhật (1 ≤ N ≤ 10000)
N dòng tiếp theo, dòng thứ i gồm 4 số Xi, Yi, Ai, Bi thể hiện tọa độ đỉnh trái trên và
đỉnh phải dưới của hình chữ nhật thứ i (-20000 ≤ Xi, Yi, Ai, Bi ≤ 20000)
7
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Output: COVER.OUT
Gồm một dòng duy nhất là đáp số của bài toán
Thời gian chạy: 0.5s
Ví dụ:
COVER.INP
COVER.OUT
5
28
-2
2
1
0
4
2
6
0
-1
5
3
2
4
6
6
5
2
3
5
1
Minh họa:
8
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Hướng dẫn:
Để tiện cho việc phân tích bài toán, chúng ta sẽ gọi hoành độ của các đỉnh hình chữ nhật là H1,
H2, …, H2*N được sắp xếp theo chiều tăng; tung độ của các đỉnh hình chữ nhật là T1, T2,
…, T2*N (giả sử các tung độ được liệt kê theo chiều tăng - ở đây chú ý rằng: chỉ có hoành độ
được sắp xếp tăng, còn tung độ là do chúng ta quy ước). Cách làm thông thường là sắp xếp H
theo chiều tăng như đã giả sử ở trên, sau đó tính diện tích ở từng khe H1H2, H2H3, …, H2*N2
1H2*N. Như vậy, độ phức tạp của thuật toán của chúng ta là O(N ), thời gian là T(N(log2N +
N)), khó có thể đáp ứng thời gian chạy là 1s. Để cho tiện, tất cả dữ liệu của chúng ta đều coi như
sắp xếp bằng Quick Sort.
Trong hoàn cảnh đó, rất may mắn, chúng có một cấu trúc dữ liệu đặc biệt khác có thể thực hiện
được điều này với độ phức tạp O(Nlog2N) và thời gian chạy là T(2Nlog2N). Đó là dùng
Interval Tree, bản chất của Interval hết sức đơn giản, chúng ta sẽ xét rõ hơn qua phân tích chi
tiết bài toán này.
Thuật toán của chúng ta về bản chất cũng giống với thuật toán vừa đề cập:
Sắp xếp các hoành độ tăng dần.
Tính diện tích che phủ từng khe H1H2, H2H3, …, H2*N-1H2*N của hoành độ, lấy tổng, ta
được đáp số của bài toán.
Trước hết, ta gán cho mỗi hoành độ đã được sắp xếp một nhãn, nhãn đó sẽ gồm Low, High lưu lại
tung độ của hình chữ nhật chứa hoành độ đó và nhãn Open. Open sẽ chứa giá trị true nếu đó là
đỉnh trên trái của hình chữ nhật, false nếu đó là đỉnh dưới phải của hình chữ nhật.
Với đề bài, ta sẽ có các hoành độ được gán nhãn (sau khi đã sắp xếp) như sau:
H[1] = -2; Label[1].Low = 0; Label[1].High = 2;
Label[1].Open = true; H[2] = -1; Label[2].Low = 2;
Label[2].High = 5; Label[2].Open = true;
...
Tiếp theo ta sẽ xây dựng một cây nhị cây nhị phân đầy đủ, mỗi đỉnh sẽ tượng trung cho số hình
chữ nhật che phủ trên đoạn [A, B] thuộc tung độ, mỗi đỉnh gồm có 2 phần Number và Cover
với ý nghĩa:
1) Number: số lượng hình chữ nhật che phủ toàn bộ [A, B]
2) Cover: tổng số đoạn tung độ bị che phủ trên đoạn [A, B]
9
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Đỉnh 1 của cây có đoạn [A, B] tương ứng là [Min, Max] (với Min, Max tương ứng là tung độ
nhỏ nhất và lớn nhất trong số các hình chữ nhật); đỉnh 2 có đoạn tương ứng [A, B] là [1, Max
div 2]; đỉnh 3 là [Max div 2, Max],… tạo thành một cây nhị phân đầy đủ. Đơn giản hơn, với
mỗi đỉnh chứa thông tin về đoạn [A, B], hai nút con tương ứng của nó sẽ lưu trữ thông tin về đoạn
[A, (A+B) div 2] và [(A+B) div 2, B]. Sở dĩ đỉnh con thứ hai không xét từ [(A+B) div 2 + 1, B] bởi
lẽ chúng ta đang xét theo tung độ chứ không phải là xét theo độ dài đoạn thẳng, nếu xét như vậy
ta sẽ không bị sót đoạn [(A+B) div 2, (A+B) div 2 + 1].
Quá trình xây dựng cây nhị phân sẽ được đồng nhất với quá trình tính diện tích, có nghĩa là với
mỗi khe H1H2, H2H3, …, H2*N-1H2*N chúng ta sẽ xây dựng cây nhị phân tương ứng với hình
chữ nhật đang xét. Lưu ý rằng “hình chữ nhật đang xét” ở đây nói về hình chữ nhật liên quan
đến các hoành độ H sau khi đã sắp xếp, bởi như đã nói ở trên, H được gán nhãn để đại diện cho
một đỉnh của hình chữ nhật.
Giả sử rằng chúng ta đang xét đến khe thứ i và i-1, đỉnh k của cây mang đoạn [A, B], có thể xảy
ra 2 trường hợp sau:
1. Đỉnh H[i] đang xét là đỉnh trái trên của hình chữ nhật: Có 3 khả năng xảy ra:
Nếu hình chữ nhật che phủ đoạn [A, B], tức là (Low ≤ A) and (B ≤ High):
10
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Khi đó số hình chữ nhật bị che phủ phải tăng lên 1 và tổng số che phủ chính bằng High –
Low. Ta không cần phải xét đến các nút con của nó.
Nếu hình chữ nhật nằm hoàn toàn ngoài đoạn [A, B], tức là (High ≤ A) or (B ≤
Low): (vì chúng ta đang xét đến tung độ nên phải thêm “=” bởi nếu có “=” thì số phần bị
che phủ cũng không tăng lên):
Khi đó, chắc chắn hình chữ nhật cũng không che phủ lên các nút con của nó, ta không
phải làm gì cả.
Nếu hình chữ nhật giao với đoạn [A, B], tức là trường hợp còn lại:
Ta xét đến các nút con của nút k. Nếu như số hình chữ nhật bao phủ lên k là 0 chứng
tỏ tổng số che phủ của k bằng tổng số che phủ của các nút con của nó.
Procedure Open_True(A, B, k, Low, High);
Begin
if A + 1 >= B then {Xét đến nút lá – trường hợp đặc biệt}
begin
if (Low <= A) and (B <= High) then Cover[k] := 1
else Cover[k] := 0;
exit;
end;
if (Low <= A) and (B <= High) then {Che phủ [A, B]}
begin
Number[k]
:=
Number[k]
+
1;
Cover[k] := B – A;
exit;
end;
{Nằm ngoài} {Giao nhau}
if (High <= A) or (B <= Low) then exit;
{Xét nút con trái}
11
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Open_True(A, (A+B) div 2, 2*k, Low, High);
{Xét nút con phải}
Open_True((A+B) div 2, A, 2*k+1, Low, High);
if Number[k] = 0 then
Cover[k] := Cover[2*k] + Cover[2*k+1];
End;
2. Đỉnh H[i] đang xét là đỉnh phải dưới của hình chữ nhật: Có 3 khả năng xảy ra:
Nếu hình chữ nhật che phủ đoạn [A, B], tức là (Low ≤ A) and (B ≤ High):
Khi đó số hình chữ nhật bị che phủ phải giảm lên 1. Nếu như không còn hình chữ nhật nào che
phủ nó thì tổng số che phủ bằng tổng số che phủ của các nút con của nó. Ta không cần phải xét
đến các nút con.
Nếu hình chữ nhật nằm hoàn toàn ngoài đoạn [A, B], tức là (High ≤ A) or (B ≤ Low): (vì
chúng ta đang xét đến tung độ nên phải thêm “=” bởi nếu có “=” thì số phần bị che phủ cũng
không tăng lên): Khi đó, chắc chắn hình chữ nhật cũng không che phủ lên các nút con của k, ta
không phải làm gì cả.
Nếu hình chữ nhật giao với đoạn [A, B], tức là trường hợp còn lại:
Ta xét đến các nút con của nút k. Nếu như số hình chữ nhật bao phủ lên k là 0 chứng tỏ tổng số
che phủ của k bằng tổng số che phủ của các nút con của nó.
Procedure Open_False(A, B, k, Low, High);
Begin
if A + 1 >= B then {Xét đến nút lá – trường hợp đặc biệt}
begin
if (Low <= A) and (B <= High) then
begin
Number[k] := Number[k] - 1;
if Cover[k] = 0 then
12
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Cover[k] := Cover[2*k] + Cover[2*k+1];
end;
exit;
end;
if (Low <= A) and (B <= High) then {Che phủ [A, B]}
begin
Number[k] := Number[k] - 1;
if Cover[k] = 0 then
Cover[k] := Cover[2*k] + Cover[2*k+1];
exit;
end;
if (High <= A) or (B <= Low) then exit; {Nằm ngoài}
{Giao nhau}
Open_False(A, (A+B) div 2, 2*k, Low, High); {Xét nút con trái}
Open_False((A+B) div 2, A, 2*k+1, Low, High); {Xét nút con
phải}
if Number[k] = 0 then Cover[k] := Cover[2*k] + Cover[2*k+1];
End;
Để tiện cho việc lưu trữ, Interval Tree của chúng ta sẽ được lưu trữ bằng mảng, đỉnh i có 2 con
là 2*i và 2*i+1.
Phần khó nhất là việc xây dựng cây đã xong, chương trình xử lý của chúng ta sẽ bao gồm sắp
xếp theo H và xét các khe H1H2, H2H3, …, H2*N-1 H2*N :
13
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Procedure Solve;
begin
Sort; {Sắp xếp dãy}
Open_True(Min,
Max,
1,
Label[1].Low,
Label[1].High); Area := 0;
for i := 2 to 2*n do
begin
Area := Area + Cover[1] * (H[i] – H[i-1]); {Tính diện
tích}
if Label[i].Open then
Open_True(Min, Max, 1, Label[i].Low, Label[i].High)
else
Open_False(Min, Max, 1, Label[i].Low,Label[i].High);
end;
end;
Chú ý:
Một số bạn sẽ cho rằng nếu như tại một hoành độ có nhiều đỉnh đóng hoặc nhiều
đỉnh mở thì sao? Câu trả lời là không sao cả, bởi lẽ lúc đó H[i] – H[i-1] sẽ bằng 0 và
diện tích sẽ không được tính vào Area. Thêm nữa, các đỉnh có chung hoành độ sẽ
được mở hoặc đóng cho đến hết rồi mới được thực sự tính vào diện tích.
Cần phân biệt Number là số hình chữ nhật phủ lên đoạn [A, B] trong một đỉnh của
cây chứ không phải số hình chữ nhật được đoạn [A, B] phủ. Sở dĩ chúng ta
cần đến Number bởi nếu có một hình chữ nhật phủ kín đoạn [A, B]
Nhiều bạn mới đọc sẽ thắc mắc: Chúng ta đang xét đến các khe, làm sao có thể xét
14
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
được hết các hình chữ nhật có chung hoành độ được? Câu trả lời nằm ở chú ý thứ
nhất: tất cả các hình chữ nhật có chung hoành độ, bất kể là đỉnh trên trái hay dưới
phải đều được xét hết trước khi diện tích được cộng chính thức vào tổng.
Loại cây mà chúng ta vừa sử dụng được gọi là Interval Tree. Vậy, Interval Tree là gì? Có thể
nói vắn tắt lại rằng Interval Tree thực chất là một loại cây nhị phân đầy đủ với mỗi đỉnh chứa
các thông tin về một đoạn [A, B] xác định. 2 con của nó chứa thông tin về đoạn [A, (A+B) div 2]
và [(A+B) div 2 + 1, B]. Tùy theo mục đích sử dụng Interval Tree mà chúng ta có các loại
Interval Tree khác nhau.
Mấu chốt của bài toán là chúng ta nhận ra được tầm quan trọng của việc xác định đoạn mở và
đoạn đóng trên một trục nhất định (ở bài toán trên chúng ta chọn trục tung). Theo cách giải thông
thường, chúng ta phải lặp để xác định sự chồng chéo nhau của các đoạn nguyên, độ phức tạp
của thuật giải thông thường là rất cao. Nhưng giờ đây với Interval Tree, độ phức tạp chỉ là
O(log2N), với trường hợp xấu nhất.
Bài tập 3: Xếp hàng(NKLINEUP)
Hàng ngày khi lấy sữa, N con bò của bác John (1 N
50000) luôn xếp hàng theo thứ tự không
đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John
sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ,
các con bò phải không quá chênh lệch về chiều cao.
Bác John đã chuẩn bị một số danh sách gồm Q (1 Q 200000) đoạn các con bò và chiều cao của
chúng (trong phạm vi [1,1000000]),. Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao
giữ con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này!
Dữ liệu
Dòng đầu tiên chứ 2 số nguyên N và Q.
Dòng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ i.
Dòng thứ i trong số Q dòng tiếp theo chứa 2 số nguyên A,B (1
A
B
N), cho biết
đoạn các con bò từ A đến B.
Kết quả
Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữ con bò thấp nhất và cao
nhất thuộc đoạn tương ứng.
15
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Ví dụ
Dữ liệu:
63
1
7
3
4
2
5
15
46
22
Kết quả
6
3
0
Thuật toán:
Đây là 1 bài toán xử lí trên dãy số và cần truy cập đến những đoạn A..B bất kì trong dãy, vì vậy
interval tree là 1 trong những lựa chọn không tồi. Bài này chúng ta có 1 điều may mắn là không
cần phải cập nhật lại chiều cao của con bò, vì vậy thông tin trong cây interval tree là cố định và ta
sẽ tạo cây interval trên dựa trên mảng chiều cao của các con bò. Mỗi đoạn thì ta cần in ra chênh
lệch độ cao con bò cao nhất và con bò thấp nhất, vì vậy chúng ta cần tìm đực giá trị lớn nhất và giá
trị nhỏ nhất trong các phần tử từ A đến B. Ta có thể dùng 1 cây interval tree với mỗi nút lưu 2
thông tin, giá trị lớn nhất và giá trị nhỏ nhất trong đoạn mà nó biểu diễn, cũng có thể dùng 2 cây
interval tree, 1 cây dùng để lưu giá trị lớn nhất, cây còn lại là giá trị nhỏ nhất. Ở đây ta gọi 2 cây
này là maxd và mind phần tạo ta có thể làm rất đơn giản dựa trên ý tưởng sau:
Nếu l=r thì Maxd[k]=Mind[k]=A[l];
Nếu không thì Maxd[k]=max(Maxd[k*2], Maxd[k*2+1]) và
Mind[k]:=min(Mind[k*2],Mind[k*2+1];
16
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Khi muốn tìm kết quả thì dựa vào bảng Maxd để tìm GTLN trên đoạn A..B, dùng mảng Mind để
tìm GTNN trên đoạn A..B, việc này làm tương tự như trong ví dụ của bài viết giới thiệu về interval
tree phía trên. Chú ý là khi tìm max hay tìm min ta đều phải đi đến những nút giống nhau( do đi
đến những nút nào thì chỉ phụ thuộc A và B) nên mỗi lần tìm chỉ cần gọi chung 1 thủ tục.
Bài tập 4: Giá trị lớn nhất(QM A X)
Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.
Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn
vị.
Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]
Giới hạn
n, m, q <= 50000
k>0
Giá trị của một phần tử luôn không vượt quá 231-1
Input
Dòng 1: n, m
m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi
Dòng thứ m+2: p
p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi
Output
Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi.
Example
Input:
62
132
463
1
34
Output:
3
17
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Thuật toán:
Bài này thì ta có m phép biến đổi tăng dãy trước rồi mới yêu cầu tìm giá trị lớn nhất trong các
đoạn chứ không phải xen kẽ nhau, vì vậy ta sẽ tìm cách xây dựng dãy số sau m phép biến đổi.
Khi có được mảng giá trị sau m phép biến đổi, công việc còn lại của ta là tạo 1 cây interval tree
với mỗi nút lưu giá trị lớn nhất của đoạn mà nó quản lí trong khi các phần tử của mảng đã xác
định, với mối truy vấn tìm GTLN thì ta có thể làm không mấy khó khăn.
Vấn đề bây giờ là xây dựng dãy số sau m phép biến đổi.
Ta có thể sử dụng 1 kĩ thuật đơn giản những rất hiệu quả như sau.
Giả sử mảng ta cần có là mảng A[0..n+1], lúc đầu A[i]=0 với mọi
i.
Mỗi yêu cầu u,v,k tức là tăng các phần tử từ vị trí u đến vị trí v lên k đơn vị, ta làm như sau:
A[u]:=A[u]+k;
A[v+1]:=A[v+1]-k;
Sau khi đọc xong m phép biến đổi và làm như trên, cuối cùng là tính mảng
A: For i:=1 to n do
A[i]:=A[i]+A[i-1];
Các bạn có thể tự chứng minh tính đúng đắn hay có thể viết đoạn chương trình này ra và kiểm
nghiệm lại. Như vậy ta đã có thể giải quyết trọn vẹn bài toán.
Bài tập 5: Giá trị lớn nhất ver2(QMAX2)
Giống bài "Giá trị lớn nhất" ở trên.
Input
- n: số phần tử của dãy (n <= 50000).
- m: số lượng biến đổi và câu hỏi (m <= 100000).
+) biến đổi có dạng: 0 x y value
+) câu hỏi có dạng : 1 x y.
Output
Ghi ra trả lời cho lần lượt từng câu hỏi.
Example
Input:
63
0133
18
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
0464
116
Output:
4
Thuật toán:
Bài này khác bài QMAX ở trên là các phép biến đổi và các câu hỏi xen kẽ nhau, vì vậy ta không
thể tạo trước 1 cây interval được. Để giải quyết bài toán này, ta cần phải thực hiện cập nhật cũng
như lấy kết quả xen kẽ nhau. Nhưng ở đây thì các công việc này không hề đơn giản.
Vừa có được kết quả, ta cũng cần phải đảm bảo 2 công việc này không được có độ phức tạp vượt
quá log(n).
Để làm bài này, ta gọi F[k] là giá trị lớn nhất trong đoạn mà nút k quản lí, trong lúc cập nhật,
muốn đảm bảo thủ tục này không vượt quá log(n) thì khi đi đến 1 nút mà nằm gọn trong đoạn
x..y thì ta không được đi vào các nút con của nó nữa( nếu không sẽ đi đến tất cả các đoạn có
trong đoạn x..y và độ phức tạp tỷ lệ với n). Nếu như vậy, ta cần có 1 mảng phụ T để lưu lại giá
trị cần tăng lên cho tất cả các phần tử của đoạn này, khi ta truy vấn đến 1 nút k đồng thời ta tăng
T[k] lên cho T[k*2], T[k*2+1] và F[k]. (do T[k] là giá trị cần tăng lên cho tất cả những phần tử
của đoạn nút k quản lí, nên các nút con của nó cũng phải tăng lên T[k]). Sau khi đã cập nhật cho
mảng F và các nút con, ta gán lại T[k]=0 để tránh trường hợp cộng lại nhiều lần. Nếu đã đến
đoạn nằm gọn trong đoạn x..y thì ta tăng mỗi biến F[k], T[k*2], T[k*2+1] lên v.
Khi muốn lấy kết quả, ta vẫn làm như bài QMAX, nhưng đến mỗi nút con, ta vẫn cần thực hiện
tăng giá trị T[k] cho T[k*2], T[k*2+1] và F[k] để lấy được kết quả. Tức là khi đến được 1 nút
nào đó( trong bất kì thao tác nào, cập nhật hay lấy kết quả) thì đều thực hiện như vậy. điều này
đảm bảo là ta có thể lấy được giá trị chính xác, đây là kiểu cây IT có thông tin truyền từ nút cha
xuống nút con. Các bạn có thể tham khảo chương trình để thấy rõ hơn.
Bài tập 6: Bật đèn(LITES)
Bác John giữ cho đàn bò thông minh bằng cách để chúng chơi các đồ chơi phát triển trí tuệ. Một
trong các trò chơi là các ngọn đèn trong chuồng. Mỗi trong số N (2 <= N <= 100,000) con bò được
đánh số từ 1..N có treo một ngọn đèn màu.
Vào đầu buổi tối, tất cả đèn đều tắt. Đàn bò điều khiển các ngọn đèn bằng N công tắc; bấm công
tắc i đổi trạng thái của đèn i từ tắt sang bật hoặc ngược lại.
19
HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE
08/2015
Đàn bò đọc và thực thi một danh sách gồm M (1 <= M <= 100,000) thao tác mô tả bởi một trong
hai số nguyên (0 <= thao tác <= 1).
Thao tác thứ nhất (mô tả bởi số 0) theo sau bởi hai số nguyên S_i và E_i (1 <= S_i <= E_i <= N)
cho biết công tắc đầu và công tắc cuối. Đàn bò sẽ bấm mỗi công tắc từ S_i đến E_i đúng một lần.
Thao tác thứ hai (mô tả bởi số 1) yêu cầu đàn bò đến xem có bao nhiêu ngọn đèn giữa S_i và E_i
(1<= S_i <= E_i <= N) đang bật. Hãy giúp bác John đảm bảo rằng đàn bò trả lời đúng bằng cách
xử lý danh sách và trả về các kết quả đúng.
Dữ liệu
* Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: N và M
* Dòng 2..M+1: Mỗi dòng chứa một thao tác với ba số nguyên cách nhau bởi khoảng trắng:
thao tác, S_i, và E_i
Kết quả
* Dòng 1..số truy vấn: Với mỗi truy vấn, in ra kết quả là một số nguyên trên một dòng.
Ví dụ
Dữ liệu:
45
012
024
123
024
114
Kết quả:
1
2
Thuật toán:
Ta có thể sử dụng INTERVAL TREE để làm như sau:
Bài này có tư tưởng khá giống với bài QMAX2, thông tin được truyền từ nút cha xuống nút con
bất cứ khi nào có thể. Ta có 1 mảng B kiểu logic, B[i]=true nghĩa là những đèn trong đoạn mà nút
thứ i quản lí cần thay đổi trạng thái. Khi đến 1 nút, nếu b[i]=true thì cần thay đổi trạng thái của
B[i*2] và B[i*2+1] đồng thời gán lại B[i]=false( đã thực hiện thay đổi rồi thì phải gán lại false),
nếu gọi mảng sl[i] là số lượng đèn đang bật trong đoạn do nút i quản lí thì nếu gặp b[i]=true phải
20
- Xem thêm -