<h1>
Range Minimum Query (RMQ) - Sparse Table
</h1>

<h2>
1. Range Minimum Query (RMQ)
</h2>

<h3>
Bài toán
</h3>

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

<h3>
Thuật trâu
</h3>

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

<h3>
Thuật cải tiến
</h3>

Ta nhận thấy để tìm min 1 đoạn ($l$,$r$) ta có thể tìm min đoạn ($l$,$x$) 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

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;
}

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;
}

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*)) [*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])$
- Khi đó độ phức tạp của bài toán sẽ là:
+ Tiền xử lý: *O*(*N* log *N*)
+ Mỗi truy vẫn *O*(*1*)
+ Có Q truy vấn, vì thế tổng độ phức tạp thời gian là *O*(*N*log*N*+*Q*)

// __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]);
}

<h2>
2. Range Sum Queries (RSQ)
</h2>

<h3>
Bài toán
</h3>

Cho mảng $A$ gồm $N$ phần tử và $Q$ truy vấn có dạng ($l$,$r$)
. Với mỗi truy vấn, in ra tổng các phần tử trong mảng $A$ từ $l$ đến $r$
. Giới hạn: $N$, $Q$ $≤$ 10^5^

<strong>Nguồn bài : [https://lqdoj.edu.vn/problem/cses1646](https://)</strong>

<strong>Nhận xét:</strong> Ta luôn có thể tách một số nguyên dương thành tổng các lũy thừa phân biệt của 2 (hệ nhị phân). VD: 18 = 2^4^ + 2^1^

Từ nhận xét trên, ta có thể tách $[l…r]$ thành log2 đoạn có độ dài 2^x^ như sau:

- Đặt $len$ = r − l + 1
- Duyệt $j$ từ 0 đến *__lg(len)*, nếu bit thứ $j$ của $len$ là $1$ thì:

+ Ta tách $[l…r]$ thành *[l…l+2^j^−1]* và *[l+2^j^…r]*
+ *l*=*l*+*2^j^* (tiếp tục tách *[l+2^j^…r]* như *[l…r]*)

// __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;
}

<h2>
3. Khi nào chúng ta nên sử dụng RMQ ?
</h2>

- Nên sử dụng RMQ cho những bài toán không có yêu cầu thay đổi các phẩn tử trong mảng do RMQ không thể giải được các bài toán đó.
- Nên sử dụng RMQ khi số lượng truy vấn $1e6$ $≤$ $Q$ $≤$ $1e7$ do độ phức tạp trong mỗi truy vấn của thuật toán này là $O(1)$ tránh bị TLE.

<h2>
4. Luyện tập
</h2>

- [Library Checker - Static RMQ](https://judge.yosupo.jp/problem/staticrmq)
- [VNOJ - AVLBIT (Dãy cấp số cộng)](https://oj.vnoi.info/problem/avlbit)
- [Codeforces - 5C (Longest Regular Bracket Sequence)](https://codeforces.com/contest/5/problem/C)
- [Codeforces - 1454F (Array Partition)](https://codeforces.com/contest/1454/problem/F)
- [Codechef - FRMQ (Chef and Array)](https://www.codechef.com/problems/FRMQ)
- [Codeforces - 475D (CGCDSSQ)](https://codeforces.com/contest/475/problem/D)
- [Codeforces - 487B (Strip)](https://codeforces.com/contest/487/problem/B)