Thuật toán Left-Right

Table of contents

1. Giới thiệu
2. Thuật toán
3. Chứng minh
4. Code
5. Ứng dụng
6. So sánh với các thuật toán khác

Giới thiệu

Thuật toán left-right thường được dùng để giải quyết bài toán sau:

Bài toán: Cho mảng $a$ gồm $n$ số. Với mỗi $1 \leq i \leq n$, tìm hai số nguyên $l[i]$ bé nhất và $r[i]$ lớn nhất sao cho $a[i] = min(a[l[i]], …, a[r[i]])$ với độ phức tạp $O(n)$.

Thuật toán

Giả sử ta tính được $l[1], l[2], …, l[i-1]$. Để tính $l[i]$, ta chạy dòng code sau

l[i] = i;
while (l[i] > 1 && a[i] >= a[l[i]-1])
    l[i] = l[l[i]-1];

Việc tìm mảng $r$ cũng được thực hiện tương tự.

Chứng minh

Tưởng tượng ta có $n$ đỉnh từ $1$ đến $n$, gốc tại $1$ và các cạnh là $i - l[i]$. Để ý là đồ thị là một cái cây. Khi tính $l[i]$, ta có thể thấy là ta nhảy trên cây. Do ta luôn bắt đầu nhảy từ $l[i]-1$, ta có thể chứng minh số lần nhảy không quá $n$.

Code

int n, a[N];

for (int i = 1; i <= n; i++) {
    l[i] = i;
    while (l[i] > 1 && a[i] >= a[l[i]-1])
        l[i] = l[l[i]-1];
}
for (int i = n; i >= 1; i--) {
    r[i] = i;
    while (r[i] < n && a[i] >= a[r[i]+1])
        r[i] = r[r[i]+1];
}

Ứng dụng

Thuật toán gần như chỉ giải quyết bài toán đã nêu.

So sánh với các thuật toán khác

Về tốc độ, dễ thấy thuật toán Left-Right nhanh-gọn-nhẹ hơn so với các thuật toán / CTDL phổ biến khác như Segment Tree hay mảng thưa đối với bài toán đã nêu.