Range Minimum Query (RMQ) – Sparse Table

1. Range Minimum Query (RMQ)

Bài toán

Cho mảng \(A\) gồm \(N\) phần tử và \(Q\) truy vấn có dạng (\(l\),\(r\)) \((N, Q ≤ 10^{5})\)

. Với mỗi truy vấn, in ra giá trị nhỏ nhất trong mảng \(A\) từ \(l\) đến \(r\)
. Ví dụ: \(A\) = \([3,6,3,9,10,2]\) \(→\) \(min[2…5] = min(6,3,9,10) = 10\)

Thuật trâu

Ta sẽ duyệt qua tất cả các phần tử có trong đoạn \((l,r)\) xem giá trị min là bao nhiêu rồi in ra giá trị đó \(O(N* Q)\)

Do đó với \(N, Q\) lớn thì thuật toán này sẽ bị TLE

Thuật cải tiến

Ta nhận thấy để tìm min 1 đoạn \((l,r)\) ta có thể tìm min đoạn \((l,r)\) và đoạn \((x + 1,r)\) rồi so sánh 2 kết quả đó với nhau xong in ra số nhỏ nhất

Cải tiến 1

Thay vì duyệt qua từng phần tử, ta có thể duyệt qua từng nhóm 2 phần tử. Từ đó, ta có thể giảm thời gian truy vấn xuống còn \(O(N/2)\)

int a[N], a2[N];
void pre() 
{
 for(int i = 1 ; i < n; ++i)
     a2[i] = min(a[i], a[i + 1]);
}
int xuly(int l, int r) 
{
 int len = r - l + 1;

 if (len == 1) return a[l];

 int mn = INT_MAX;
 for(int i = l ; i < r ; i += 2) mn = min(mn, a2[i]);

 // khi kết thúc vòng lặp phía trên, có thể còn 1 số phần tử chưa được xét
 // ví dụ [l, r] = [3, 7], ta chỉ mới xét a[3...6] chứ chưa xét a[7]
 // do đó ta chỉ cần xét thêm a2[r - 1] nữa là đủ do a2[r - 1] = min(a[r - 1], a[r])
 // gtri vẫn nằm trong đoạn [l, r] mà đề bài yêu cầu

 mn = min(mn, a2[r - 1]);

 return mn;
}

Cải tiến 2

Tiếp tục cải tiến như phần 1: Thay vì duyệt qua từng nhóm 2 phần tử, ta có thể duyệt qua từng nhóm 4 phần tử. Từ đó, ta có thể giảm thời gian truy vấn xuống còn \(O(N/4)\)

int a[N], a2[N], a4[N];
void pre() 
{
    for(int i = 1 ; i < n; ++i)
        a2[i] = min(a[i], a[i + 1]);

     for(int i = 1 ; i + 3 <= n; ++i)
        a4[i] = min(a2[i], a2[i + 1]);
}
int xuly(int l, int r) 
{
    int len = r - l + 1;

    if (len == 1) return a[l];

    else if (len < 4)
    {
        return min(a2[l], a2[r - 1]);
        // do a[l, l + 1] và a[r - 1, r] sẽ nằm trong đoạn [l, r] mà đề bài yêu cầu
    }

    int mn = INT_MAX;
    for(int i = l ; i + 3 <= r ; i += 4) mn = min(mn, a4[i]);

    // tương tự như phần 1 với những TH thiếu 1 số số chưa được xét ta chỉ cần xét thêm a4[r - 3] là đủ 

    mn = min(mn, a4[r - 3]);

    return mn;
}

Cải tiến 3

Cứ tiếp tục như vậy ta sẽ tối ưu thuật toán đến \(log_{2} N\)

• Nếu dùng mảng \(a[log_{2} N]\) thì rất loằng ngoằng => dễ nhầm lẫn.
• Ta có thể gọi:
  • \(st[j][i]\) là giá trị lớn nhất của \(2^{j}\) phần tử tính từ i(min của \(a[i…i+2^{j}−1])\), tương ứng với \(a(2^{j})\)[i]
  • Ta có :
    Nếu \(j = 0\) => \(st[j][i] = a[i]\)
    Nếu \(j > 0\) => \(st[j][i] = min(st[j−1][i],st[j−1][i+2j−1])\)

// __lg(x) là hàm trả về log2 của x
// ví dụ: N = 10^5 thì __lg(N) = 16 vì 2^16 = 65536
// LOG = __lg(N)

int a[N], st[LOG + 1][N];

void pre() 
{
    for(int i = 1 ; i <= n ; ++i) st[0][i] = a[i];

    for(int j = 1 ; j <= LOG ; ++j)
        for(int i = 1 ; i + (1 << j) - 1 <= n ; ++i)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}

int xuly(int l, int r) 
{
    int x = __lg(r - l + 1);

    return min(st[x][l], st[x][r - (1 << x) + 1]);
}

// __lg(x) là hàm trả về log2 của x
// ví dụ: N = 10^5 thì __lg(N) = 16 vì 2^16 = 65536
// LOG = __lg(N)

int a[N], st[LOG + 1][N];

void pre() 
{
    for(int i = 1 ; i <= n ; ++i) st[0][i] = a[i];

    for(int j = 1 ; j <= LOG ; ++j)
        for(int i = 1 ; i + (1 << j) - 1 <= n ; ++i)
            st[j][i] = st[j - 1][i] + st[j - 1][i + (1 << (j - 1))];
}

int xuly(int l, int r) 
{
    int len = r - l + 1;
    int s = 0;

    for(int j = 0 ; (1 << j) <= len ; ++j)
    {
        if (len >> j & 1) 
        {
            s = s + st[j][l];
            l = l + (1 << j);
        }
    }

    return sum;
}