Không mất tổng quát ta xét bài toán tìm min.

Để giải quyết bài toán này ta có thể dùng interval tree với độ phức tạp cho mỗi yêu cầu là O(logN) và khởi tạo trong O(NlogN) nhưng 1 cách tốt hơn là dùng RMQ.

Ở đây xin đề cập tới phương pháp dùng RMQ với độ phức tạp O(NlogN) để khởi tạo và O(1) để trả lời 1 yêu cầu. Ngoài ra, cũng có 1 cách khác dùng RMQ với độ phức tạp để khởi tạo chỉ còn là O(N) nhưng khá tốn bộ nhớ và rất phức tạp.

Tư tưởng thuật toán là chia để trị. Ta cần 1 mảng RMQ với bộ nhớ O(NlogN) như sau: với mỗi i,j: R[i,j] là giá trị min trong đoạn từ i tới i+2^j-1 (1<=i<=N, 1<=j<=logN, i+2^j-1<=N). Tức là từ 1 vị trí i bất kì ta tính trước min các đoạn có độ dài là luỹ thừa của 2. Giả sử đã có mảng R, ta dễ dàng tìm giá trị min trong đoạn từ U tới V bằng cách KQ:=min(R[u,k],R[v-2^k+1,k]) trong đó k là GTLN thoả mãn 2^k<=V-U+1.

Có thể thấy đoạn [u..v] đã bị phủ bởi 2 đoạn nhỏ [u..u+2^k-1] và [v-2^k+1..v] vì tổng độ dài 2 đoạn đó là 2^k+1>v-u+1 mà 2 đoạn này chỉ gồm các phần tử thuộc trong đoạn [u..v]. Vậy giá trị KQ tìm được ở trên chính là min(u,v).

Vấn đề còn lại là khởi tạo mảng R trong O(NlogN) như thế nào? từ công thức tìm min trên ta có thể dễ dàng suy ra cách khởi tạo mảng R: R[i,j]=min(R[i,j-1],R[i+2^j,j-1]

Đây là thủ tục khởi tạo mảng R:

Procedure khoitao;

Var i,j,k:longint;

Begin

For i:=1 to N do R[i,0]:=A[i]; {với j=1}

K:=trunc(ln(N)/ln(2));{ln(N)/ln(2)=log(N)}

For j:=1 to k do

For i:=1 to n-1 shl j+1 do {1 shl j=2^j}

If R[i,j-1]

End;

Và để tìm min đoạn từ vị trí i tới vị trí j ta dùng Function FindMin sau:

Function Findmin(i,j:longint):longint;

Var k:longint;

Begin

K:=trunc(ln(j-i+1)/ln(2));

If R[i,k]

else FindMin:=R[j-1 shl k+1,k];

End;

RMQ là 1 cách tiếp cận thông minh bài toán trên. Nhưng ứng dụng của RMQ không lớn và đa dạng bằng các cấu trúc khác, cách sử dụng RMQ chủ yếu là đưa bài toán trở về bài toán trên và giải bằng RMQ. Nhưng tư tưởng chia để trị như của RMQ thì có ứng dụng trong khá nhiều bài toán khác.

Sau đây là 1 ví dụ về ứng dụng của RMQ: trong bài toán tìm LCA (least common ancestor) - tổ tiên chung gần nhất của 2 nút U,V trên 1 cây cho trước. Với 2 nút U,V thì LCA(u,v) là nút cao nhất mà là tổ tiên của cả u và v.

Bài toán: cho 1 cây gồm N nút. Có 1 số yêu cầu trả về nút là tổ tiên chung gần nhất của cặp nút U,V.

Phương pháp giải:

Gọi mảng H[i] là độ cao của nút I, hay nói cách khác là độ dài đường đi từ gốc tới nút I. Đầu tiên cần chuyển bài toán tìm LCA về bài toán đã nêu. Nhận xét: trên đường đi từ U tới V thì nút có độ cao nhỏ nhất chính là cha chung của U và V.

Xét mảng B được xây dựng như sau:

Procedure ktB(i:longint);

Begin

Inc(m);B[m]:=i;C[i]:=m;

For j {thuộc tập con của i} do ktB(j);

If cha[i]<>0 then begin Inc(m);B[m]:=cha[i];end;

End;

M là số phần tử của mảng B, khởi tạo m:=0;

Mảng B gọi là 1 Euler tour trên cây đã cho, xây dựng bằng cách DFS từ gốc, đi qua 1 nút thì thêm nút đó vào trong mảng B. Độ phức tạp khởi tạo mảng B bằng độ phức tạp của thuật toán DFS tức là O(N) đối với cây nếu dùng danh sách liên kết động. Số phần tử của B là m=2*n. Mảng C lưu lại vị trí của I trong mảng B. Nhận xét thấy giá trị LCA(u,v) chính là nút, hay phần tử của B trong đoạn từ C[u] tới C[v] có độ cao đạt min. Nếu như vậy dựa vào mảng B,H và dùng RMQ dễ dàng xác định được LCA(u,v). Cài đặt RMQ trong trường hợp này khác 1 chút ở điểm giá trị so sánh là H[] chứ không phải là B[], rất dễ nhầm lẫn trong cài đặt. Giả sử đã có mảng B[],C[] và H như mô tả, sau đây là code thể hiện thuật toán tìm LCA dựa vào RMQ.

Procedure khoitaoR;

Var i,j,k:longint;

Begin

For i:=1 to M do R[i,0]:=B[i]; {với j=1}

K:=trunc(ln(M)/ln(2));

For j:=1 to k do

For i:=1 to M-1 shl j+1 do

If H[R[i,j-1]]

else R[i,j]:=R[i+1 shl j,j-1];

End;

Function LCA(i,j:longint):longint;

var i,j,k,tg:longint;

Begin

I:=C[i];J:=C[j];

If i>j then

begin

tg:=i;

i:=j;

j:=tg;

end; {buộc i<=j}

K:=trunc(ln(j-i+1)/ln(2));

If H[R[i,k]]

else LCA:=R[j-1 shl k+1,k];

End;

Sau khi khởi tạo mảng R, function LCA(i,j) sẽ trả về giá trị là LCA của 2 nút i,j.

Vấn đề còn lại là chứng minh tính đúng đắn của thuật toán trên:

Gọi T=LCA(U,V). Giả sử trong quá trình DFS, U được xét tới trước V. Dựa vào thuật toán DFS suy ra trong mảng B từ vị trí của U tới vị trí của V chắc chắn chứa T và T là đỉnh thấp nhất. Vì nếu có đỉnh thấp hơn T thì quá trình DFS đã đi ra ngoài cây gốc T nên chắc chắn đã xét qua V. Như vậy, thuật toán trên là thuật toán đúng đắn.

Độ phức tạp thuật toán là O(N) khởi tạo B + O(2Nlog(2*N)) khởi tạo RMQ và O(1) cho mỗi yêu cầu tìm LCA(u,v).

Ngoài ra, RMQ còn ứng dụng trong tìm LCP – longest common prefix của 2 suffix khi sử dụng Suffix Array xin đề cập tới trong 1 tài liệu khác nói về suffix array.

Bài tập:

1. Cài đặt hoàn chỉnh 2 bài toán trên.

2. Bài QTREE2 (SPOJ).

Cho trước 1 cây với các cạnh vô hướng gồm N (N<= 10000) đỉnh, các cạnh được đánh số từ 1 tới N-1. Mỗi cạnh có 1 độ dài cạnh cho trước. Viết chương trình thực hiện 1 nhóm yêu cầu thuộc 1 trong 2 kiểu sau:

DIST a b : hỏi khoảng cách giữa 2 nút a và b - tức là độ dài đường đi từ a tới b.

KTH a b k: hỏi đỉnh thứ k trên đường đi từ a tới b.

Input: Dòng đầu tiên ghi số N. Trong 1 số dòng tiếp theo mỗi dòng ghi 1 yêu cầu thuộc 1 trong 2 dạng yêu cầu trên. Input được kết thúc bởi 1 dòng ghi “DONE”.

Output: Với mỗi yêu cầu ghi ra kết quả trên 1 dòng của file output.

VD:

Input

6

1 2 1

2 4 1

2 5 2

1 3 1

3 6 2

DIST 4 6

KTH 4 6 4

DONE

Output

5

3

Đoàn Mạnh Hùng
Manhhung741@yahoo.com

School@net (Theo THNT)