Phạm vi truy vấn tối thiểu theo phương pháp <O(n), O(1)> (từ cây đến hạn chế RMQ)

Question

Vì vậy, tôi đọc this Hướng dẫn TopCoder về RMQ (Phạm vi truy vấn tối thiểu) và tôi có một câu hỏi lớn.

Trên phần mà ông giới thiệu approach, những gì tôi có thể hiểu được cho đến bây giờ là thế này:

(Cách tiếp cận toàn bộ thực sự sử dụng phương pháp giới thiệu trong Sparse Table (ST) Algorithm, Reduction from LCA to RMQ và from RMQ to LCA)

Với một mảng A [N], chúng ta cần phải biến đổi nó thành một cây Cartesian, do đó làm cho một vấn đề RMQ một vấn đề LCA (tổ tiên chung thấp nhất). Sau đó, chúng tôi có thể nhận được một phiên bản đơn giản của mảng A, và làm cho nó một vấn đề hạn chế RMQ.

Vì vậy, về cơ bản nó là hai biến đổi. Vì vậy, RMQ đầu tiên để LCA một phần là đơn giản. Bằng cách sử dụng một ngăn xếp, chúng ta có thể thực hiện phép biến đổi trong thời gian O (n), dẫn đến một mảng T [N] trong đó T [i] là phần tử cha của phần tử i. Và cây đã hoàn thành.

Nhưng dưới đây là những gì tôi không thể hiểu được. Cách tiếp cận O (n) cần một mảng trong đó |A[i] - A[i-1]| = 1 và mảng đó được giới thiệu trong phần Reduction from LCA to RMQ của hướng dẫn. Điều đó liên quan đến một tour du lịch Euler của cây này. Nhưng làm thế nào điều này có thể đạt được với kết quả cuối cùng của tôi từ biến đổi? Cách tiếp cận của tôi với nó không phải là tuyến tính, vì vậy nó nên được coi là xấu trong cách tiếp cận này, những gì sẽ là cách tiếp cận tuyến tính cho điều này?

UPDATE: Điểm mà nhầm lẫn tôi

Here's the array A[]: 

    n : 0 1 2 3 4 5 6 7 8 9 
A[n]: 2 4 3 1 6 7 8 9 1 7 

Here's the array T[]: 

    n : 0 1 2 3 4 5 6 7 8 9 
T[n]: 3 2 0 * 8 4 5 6 3 8 // * denotes -1, which is the root of the tree 

//Above is from RMQ to LCA, it's from LCA to RMQ part that confuses me, more below. 

Một bức tranh của cây:

Một Euler Tour cần biết con của mỗi nút, giống như một DFS (Depth- Tìm kiếm đầu tiên) trong khi T [n] chỉ có gốc của mỗi phần tử, không phải là con.

Answer 1

Đây là hiểu biết hiện tại của tôi về những gì đang gây nhầm lẫn bạn:

1. Để giảm RMQ để LCA, bạn cần phải chuyển đổi mảng vào một cái cây và sau đó làm một tour du lịch Euler của cây đó.
2. Để thực hiện chuyến tham quan Euler, bạn cần lưu trữ cây sao cho mỗi nút trỏ vào con của nó.
3. Mức giảm được liệt kê từ RMQ sang LCA có mỗi điểm nút cho phụ huynh của nó, không phải là điểm nút của cha mẹ.

Nếu trường hợp này xảy ra, mối quan tâm của bạn hoàn toàn hợp lý, nhưng có cách dễ dàng để khắc phục điều này. Cụ thể, một khi bạn có mảng của tất cả các con trỏ cha, bạn có thể chuyển đổi nó thành một cây nơi mỗi nút trỏ đến con của nó trong thời gian O (n). Ý tưởng là như sau:

• Tạo một mảng nút n. Mỗi nút có một trường giá trị, một con trái và một con đúng.
• Ban đầu, hãy đặt nút thứ n để có con trái, con phải, và giá trị của phần tử thứ n từ mảng.
• Lặp lại trên mảng T (trong đó T [n] là chỉ số chính của n) và thực hiện như sau:
  • Nếu T [n] = *, thì mục thứ n là gốc. Bạn có thể lưu trữ để sử dụng sau này.
  • Nếu không, nếu T [n] < n, thì bạn biết rằng nút n phải là con phải của cha mẹ của nó, được lưu trữ tại vị trí T [n]. Vì vậy, hãy đặt nút con phải của nút T [n] thành nút thứ n.
  • Nếu không, nếu T [n]> n, thì bạn biết rằng nút n phải là con trái của cha mẹ của nó, được lưu trữ tại vị trí T [n]. Vì vậy, hãy đặt con trái của nút T [n] thành nút thứ n.

Điều này chạy theo thời gian O (n), vì mỗi nút được xử lý chính xác một lần.

Khi việc này được thực hiện, bạn đã xây dựng một cách rõ ràng cấu trúc cây mà bạn cần và có một con trỏ đến thư mục gốc. Từ đó, nó phải được hợp lý đơn giản để tiến hành với phần còn lại của thuật toán.

Hy vọng điều này sẽ hữu ích!