Sparce Table

概要

長さ $n$ の配列 $a$ が与えられたとき，$w = 1, 2, 4, 8, \ldots, \lfloor \log_2 n \rfloor$ に対し $\min_{i \in [0,w)} a[i], \min_{i \in [1, w+1)} a[i], \ldots, \min_{i \in [n-w, n)} a[i]$ を事前に計算しておく．すると，区間 $[l, r)$ が与えられたときに区間の最小値を $O(1)$ で計算できる．

使い方

sparce_table<T> st(begin, end): 半開区間 [begin, end) を管理する sparce table を作る．
st.rmq(x, l, r): x[l, r) の最小値の インデックス を返す．

計算量

構築 : 軽めの $O(n \log n)$, クエリ $O(1)$

実装

template <typename T>
struct sparce_table {
    using size_t = std::size_t;
    template <typename U>
    using vector = std::vector<U>;

    size_t sz;
    vector<vector<size_t>> min;
    vector<size_t> log2;

    sparce_table() {}

    template <typename iterator>
    sparce_table(iterator first, iterator last)
        : sz(distance(first, last)), min(1, vector<size_t>(sz)) {
        initialize(first);
    }

    template <typename iterator>
    void initialize(iterator dat) {
        log2.resize(sz + 2);
        log2[1] = 0;
        for (size_t i = 2; i < sz + 2; ++i) {
            log2[i] = log2[i / 2] + 1;
        }
        if (sz) min.reserve(log2[(sz + 1) / 2] + 2);
        std::iota(min[0].begin(), min[0].end(), 0);
        for (size_t i = 1; i < 30; ++i) {
            size_t w = 1 << i;
            if (sz + 1 < w) break;
            vector<size_t> next(sz + 1 - w);
            for (size_t l = 0; l < sz + 1 - w; ++l) {
                size_t left = min[i - 1][l], right = min[i - 1][l + w / 2];
                next[l] = dat[left] < dat[right] ? left : right;
            }
            min.emplace_back(move(next));
        }
    }

    template <typename Container>
    size_t rmq(Container const &x, size_t l, size_t r) const {
        size_t i = log2[r - l];
        size_t rr = r - (1 << i);
        l = min[i][l], r = min[i][rr];
        return x[l] < x[r] ? l : r;
    }
};