Sự liên hệ giữa bài toán LCA và bài toán RMQ

by **pkt_zz** 13/6/2010, 2:26 am

Nguồn: [You must be registered and logged in to see this link.]
Bài toán LCA ( Least Common Ancestor ) :

Đầu vào : 1 cây với n đỉnh.

Chất vấn : với 2 nút u, v bất kỳ của cây T, chất vấn LCA(u,v) cho biết cha chung gần nhất của 2 đỉnh u,v trong cây T, tức là cho biết đỉnh xa gốc nhất là cha của cả u, v.

Bài toán RMQ ( Range Minimum Query ) :

Đầu vào : 1 mảng A với n số.

Chất vấn : với 2 chỉ số i và j, chất vấn RMQ(i,j) cho biết chỉ số của phần tử nhỏ nhất trong mảng con A[i…j].

Các bài toán chất vấn nếu cần thời gian chuẩn bị là f(n) và thời gian trả lời mỗi chất vấn là g(n) thì độ phức tạp của thuật toán sẽ là .

Bổ đề : Nếu có 1 thuật toán với độ phức tạp là cho bài toán LCA thì sẽ có 1 thuật toán với độ phức tạp là cho bài toán RMQ.

Chứng minh :

Giả sử ta có mảng A[1…n] là mảng đầu vào của bài toán RMQ. Ta sẽ xây dựng 1 cây theo cách sau : gốc của cây sẽ tương ứng với phần tử nhỏ nhất của mảng A; sau khi loại bỏ phần tử này đi, mảng A sẽ chia thành 2 phần; con trái và con phải của gốc được xây dựng tương tự từ 2 mảng con bên trái và bên phải mảng ban đầu.

Để xây dựng được cây này ta mất thời gian là O(N). Gọi Ti là cây tương ứng với mảng A[1…i], để xây dựng cây Ti+1 ta để ý rằng nút i+1 sẽ thuộc đường đi xuất phát từ gốc và luôn đi sang bên phải (gọi là đường Pr). Vì thế ta sẽ đi theo đường này từ dưới lên trên cho đến khi gặp vị trí thích hợp để chèn nút i+1 vào. Các nút bên dưới sẽ trở thành con trái của nút i+1. Để ý rằng mỗi lần kiểm tra xem 1 vị trí có thích hợp để chèn nút mới vào không, ta sẽ thêm vào hoặc loại bỏ 1 nút từ đường Pr, và 1 nút chỉ có thể được thêm vào và loại bỏ khỏi đường Pr nhiều nhất 1 lần. Vì thế ta xây dựng cây sẽ mất O(N).

Sau khi xây dựng cây, gọi k = LCA(i,j) với i,j bất kỳ. Như thế k sẽ là nút đầu tiên chia cắt i,j. Theo cách xây dựng cây thì k chính là phần tử nhỏ nhất của mảng con A[i…j]. Vì thế RMQ(i,j) = LCA(i,j).

Như thế để tính RMQ(i,j) ta mất O(N) ở bước chuẩn bị để xây dựng cây và O(1) để gọi thủ tục LCA(i,j) trên cây. Bổ đề được chứng minh.

Bổ đề : Nếu có 1 thuật toán với độ phức tạp là cho bài toán RMQ thì sẽ có 1 thuật toán với độ phức tạp là cho bài toán LCA.

Chứng minh :

Giả sử ta có 1 cây T là cây đầu vào của bài toán LCA. Dùng thủ tục DFS cho cây này và viết ra các đỉnh của cây mỗi khi đỉnh đó được đi qua. Khi đó ta sẽ nhận được 1 dãy 2*n-1 số bởi vì chúng ta bắt đầu liệt kê từ đỉnh gốc, với mỗi cạnh ta sẽ liệt kê được 2 đỉnh ( ở lần đi và lần về ). Có n-1 cạnh nên số đỉnh sẽ là 2*(n-1)+1.

Gọi mảng E[1…2n-1] là mảng ghi danh sách các đỉnh được thăm bằng cách DFS trên.

Khởi tạo mảng L[1…2n-1], L[i] cho ta biết khoảng cách từ nút E[i] tới gốc của cây.

Khởi tạo mảng R[1…n], R[i] cho ta biết vị trí xuất hiện của số i trong mảng E. Nếu số i xuất hiện nhiều lần thì ta lấy vị trí nào cũng được.

Dựa vào nhận xét : LCA của 2 nút u và v chính là nút có khoảng cách tới gốc nhỏ nhất trong số các nút xuất hiện từ lúc ta thăm tới u cho đến khi ta thăm tới v.

Thực hiện thao tác i = RMQ(R[u], R[v]) trên mảng L, khi đó i sẽ là chỉ số của phần tử nhỏ nhất trong khoảng L[R[u]…R[v]], E[i] cho ta kết của của phép chất vấn LCA(u,v).

Như thế để tính LCA(u,v) ta mất O(n) để khởi tạo các mảng E,L,R. và mất O(1) để gọi thủ tục RMQ(R[u],R[v]). Bổ đề được chứng minh.

Nhận xét : bài toán RMQ phát sinh khi giải bài toán LCA chỉ là 1 trường hợp đặc biệt của bài toán RMQ tổng quát bởi các phần tử liên tiếp nhau trong mảng hơn kém nhau đúng 1 đơn vị. ( Do 2 phần tử liên tiếp là khoảng cách tới gốc của 2 nút có quan hệ cha con với nhau ). Bài toán này gọi là ±1RMQ.

Để giải bài toán RMQ ta có thể sử dụng cấu trúc dữ liệu Interval Tree. Khi đó thuật toán sẽ có độ phức tạp là và sử dụng O(N) bộ nhớ. Một thuật toán khác nhanh hơn với độ phức tạp là sẽ được trình bày dưới đây:

Gọi F[i,j] = RMQ(i,i+2^j-1). Ta có thể khởi tạo mảng F trong thời gian NlogN bằng cách sử dụng QHĐ. Khi đó RMQ(i,j) = F[i,t] nếu A[F[i,t]] < A[F[j-2^t+1,t]] và RMQ(i,j) = F[j-2^t+1,t] nếu ngược lại với t = Trunc(Log(j-i+1)).

Cũng với phương pháp trên và một số cải tiến ta có thể giải bài toán ±1RMQ trong như sau :

Giải sử A là mảng đầu vào của bài toán ±1RMQ. Chia mảng A thành các block liên tiếp với độ dài là logN/2. Định nghĩa mảng A’[1…2*N/LogN] với A’[i] cho ta biết giá trị nhỏ nhất của block thứ i và B[1…2*N/LogN] với B[i] là vị trí mà giá trị A’[i] xuất hiện trong block đó. Sử dụng thuật toán trên với mảng A’ ta sẽ có thuật toán với độ phức tạp là . Để thực hiện chất vấn RMQ(i,j) trên mảng A, nếu i,j thuộc các block khác nhau thì ta sẽ làm như sau :

- Tìm min của đoạn từ i đến phần cuối của block chứa i

- Tìm min của các block nằm giữa block chứa i và block chứa j

- Tìm min của đoạn từ đầu block chứa j đến j

Thao tác thứ 2 hoàn toàn có thể thực hiện trong dựa vào mảng A’ và B. Vì vậy ta chỉ cần quan tâm đến trường hợp i,j nằm trên cùng 1 block.

Để ý 1 block có 2 đặc trưng : 1 là giá trị của phần tử đầu tiên, 2 là dãy nhị phân ứng với mỗi phần tử của block cho ta biết nó lớn hơn hay nhỏ hơn phần tử trước. Nếu 2 block có cùng đặc trưng 2 thì ta có thể sử dụng kết quả chất vấn của block này để xác định kết quả chất vấn của block kia. Số đặc trưng 2 chỉ vào khoảng 2^(logN/2-1) = O(sqrt(N)) là rất nhỏ, vì thế ta có thể xác định trước các đặc trưng 2 cũng như kết qủa của tất cả các câu chất vấn chỉ mất O( sqrt(N)*LogN*LogN). Với N đủ lớn ta có thể coi sqrt(N)*Log(N)*Log(N) < N ( nếu muốn ta có thể sử dụng các block với độ dài là LogN/3, LogN/4 để đạt được bất đẳng thức này). Để xác định đặc trưng 2 của các block trong A cũng chỉ mất O(N) khi khởi tạo. Vì thế bài toán ±1RMQ có thể giải quyết trong với bộ nhớ là O(N).

Với thuật toán ±1RMQ ta có thể đưa ra được thuật toán LCA và thuật toán RMQ tổng quát cũng với thời gian .