# RMQ

## 前言

應該對 $\text{RMQ}$ 都不陌生
底下都以 $\text{Range Minimum Query}$ 為例

## 暴力

用 $\text{for}$ 迴圈硬跑，單次複雜度是 $\mathcal{O}(n)$

int mn = 1e18;
for (int i = l; i < r; i++)
{
    mn = min(mn, v[i]);
}

## 也是暴力

用兩層 $\text{for}$ 迴圈處理所有可能的詢問
要查就直接查表
預處理 $\mathcal{O}(n^2)$ 查詢 $\mathcal{O}(1)$

vector<vector<int>> ans(n, vector<int>(n, 1e18));
for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        if (i == j)
            ans[i][j] = v[j];
        else
            ans[i][j] = min(v[j], ans[i][j - 1]);
    }
}

## 單調隊列

[**1995 . 桑京邀請賽**](https://tioj.ck.tp.edu.tw/problems/1995)

將詢問離線並照右界排序
維護一個單調遞增的 $\text{Stack}$
並在它上面用左界做二分搜
總複雜度 $\mathcal{O}(n+q\log n)$

struct qu
{
    LL l, r, id;
    qu(LL _l, LL _r, LL _id) : l(_l), r(_r), id(_id) {}
    qu() {}
    bool operator<(const qu &o) const
    {
        if (r == o.r)
            return l < o.l;
        return r < o.r;
    }
};

void sol()
{
    LL n, q;
    scanf("%d%d", &n, &q);

    qu ask[q];
    for (int i = 0; i < q; i++)
    {
        LL l, r;
        scanf("%d%d", &l, &r);
        --l, --r;
        ask[i] = qu(l, r, i);
    }
    sort(ask, ask + q);

    vector<pLL> st;
    LL ptr = 0;
    LL a;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a);
        while (!st.empty() && st.back().S < a)
        {
            st.pop_back();
        }
        st.pb({i, a});
        while (ask[ptr].r == i)
        {
            auto x = ask[ptr];
            pLL temp = {x.l, -10};
            ask[ptr].l = lower_bound(all(st), temp)->S;
            ask[ptr].r = ask[ptr].id;
            ptr++;
        }
    }
    sort(ask, ask + q);
    for (int i = 0; i < q; i++)
    {
        printf("%d\n", ask[i].l);
    }
}

## 分塊

維護每塊的最小值
把詢問的區間拆成兩部分：
包含完整的塊、不包含完整的塊（左右兩側）
包含完整的塊就直接拿維護好的最小值
不包含完整的塊直接暴力跑
假設大小為 $S$，詢問複雜度為 $\mathcal{O}(\frac{n}{S}+S)$
根據算幾不等式，$S=\sqrt n$ 時有最小值
可以帶修改

## Sparse Table

用倍增來處理詢問
預處理的複雜度 $\mathcal{O}(n\log n)$
單次詢問複雜度 $\mathcal{O}(1)$

struct sprase_table
{
    LL n;
    vector<vector<LL>> sp;
    sprase_table(vector<LL> &v) : n(v.size())
    {
        sp.rz(20, vector<LL>(n));
        for (int i = 0; i < n; i++)
        {
            sp[0][i] = v[i];
        }
        for (int i = 1; i < 20; i++)
        {
            for (int j = 0; j + (1 << i) - 1 < n; j++)
            {
                sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i)-1)]);
            }
        }
    }
    LL ask(LL l, LL r) // [l, r) 0 - based
    {
        return min(sp[__lg(r - l)][l], sp[__lg(r - l)][r - (1 << __lg(r - l))]);
    }
};

## Four Russian

把陣列分塊
每塊都有一個 $\text{Sparse Table}$
再把每塊的最小值塞進另一個 $\text{Sparse Table}$
這樣當左右界在不同塊時就只需要跑三個 $\text{Sparse Table}$ 再取極值就好
那每塊大小要設多少？

假設每塊大小為 $S$，一共有 $\frac{n}{S}$ 塊，預處理複雜度為 $\mathcal{O}(\frac{n}{S}(S\log S)+\frac{n}{S}\log \frac{n}{S})$
$=\mathcal{O}(n\log S+\frac{n}{S}\log \frac{n}{S})$

根據算幾不等式，最小值發生在 $n\log S=\frac{n}{S}\log \frac{n}{S}$

整理後得出 $S=\log_S n - 1$
所以取 $S=\log n$
預處理複雜度為 $\mathcal{O}(n\log\log n)$
如果預處理好每塊的前後綴最小值就只需要跑一個 $\text{Sparse Table}$ 就好

## ±1 RMQ

對於陣列 $v$，$|v[i]-v[i+1]|=1,\ i=1,\ 2,...,\ n-1$ 皆成立
這裡要想辦法優化預處理的複雜度

大的 $\text{Sparse Table}$ 複雜度是 $\mathcal{O}(\frac{n}{\log n}\log \frac{n}{\log n})=\mathcal{O}(n-\frac{n}{\log n}\log \log n)<\mathcal{O}(n)$
所以要想辦法優化每塊的複雜度

因為每塊的大小只有 $\log n$
能不能像上面一樣用 $\mathcal{O}(\log^2 n)$ 的時間打表？
又注意到大小只有 $\log n$，而我們是依靠上升或下降來比較最大最小值
總共只會有 $2^{\log n}=n$ 種情形
所以小塊的複雜度最多也只有 $\mathcal{O}(n)$

預處理 $\mathcal{O}(n)$ 查詢 $\mathcal{O}(1)$

## $\mathcal{O}(n)-\mathcal{O}(1)$

1. 把數列轉換成笛卡兒樹
2. 用歐拉迴路求 $\text{LCA}$
3. 因為歐拉迴路的各點深度滿足 $\text{±1 RMQ}$ 的限制，所以可以把所有 $\text{RMQ}$ 等價成 $\text{±1 RMQ}$
4. 所以 $\text{RMQ}$ 所有演算法最好的複雜度為 $\mathcal{O}(n)-\mathcal{O}(1)$

## 更簡單的 $\mathcal{O}(n)-\mathcal{O}(1)$

一樣先分成 $\frac{n}{\log n}$ 塊，每塊的大小是 $\log n$
用跟 $\text{Four Russian}$ 一樣的方法，現在著重考慮 $l,\ r$ 在同一塊的詢問

回想起利用 $\text{Stack}$ 的作法，但是把 $\text{Stack}$ 的狀態替換成一個 $\text{bool}$ 陣列
$1,\ 0$ 代表他在不在 $\text{Stack}$ 中
而這陣列可以用一個整數的二進制來表示
所以每塊有 $\log n$ 個整數代表當走到 $i$ 時每個數字的狀態
再來，可以用位元運算找到第 $l$ 位後第一個 $1$ 的位置
這樣就完成了
如果 $\log n>64$ 就改用 $\text{bitset}$

## 線段樹

應該都會吧？
單次詢問複雜度 $\mathcal{O}(\log n)$
可以帶修改

struct seg
{
    LL l, r, v;
    seg *ln, *rn;
    seg(LL ll, LL rr) : l(ll), r(rr)
    {
        if (l != r - 1)
        {
            LL m = (l + r) >> 1;
            ln = new seg(l, m);
            rn = new seg(m, r);
            v = comb(ln->v, rn->v);
        }
        return;
    }
    LL comb(LL a, LL b)
    {
      return min(a, b);
    }
    LL ask(LL ll, LL rr)
    {
        if (l == ll && r == rr)
        {
            return v;
        }
        LL m = (l + r) >> 1;
        if (m >= rr)
        {
            return ln->ask(ll, rr);
        }
        else if (m <= ll)
        {
            return rn->ask(ll, rr);
        }
        else
        {
            return comb(ln->ask(ll, m), rn->ask(m, rr));
        }
    }

    void revise(LL tar, LL value)
    {
        if (tar == l && tar == r - 1)
        {
            v = value;
            return;
        }
        else
        {
            LL m = (l + r) >> 1;
            if (tar < m)
            {
                ln->revise(tar, value);
            }
            else
            {
                rn->revise(tar, value);
            }
            v = comb(ln->v, rn->v);
        }
    }
};

## 沒了