My Algorithm : kopricky アルゴリズムライブラリ

Sparse Table

コードについての説明

静的 RMQ(更新のない区間最小値クエリ) に $\O (1)$ で答えるデータ構造を $\O (n \log n)$ 時間で構築するアルゴリズム.
「 $table[k][i]$ : インデックス $i$ から始まる $2^k$ 個の要素の中の最小値」という配列を $\O (n \log n)$ かけて前計算しておけば区間 $[l,r)$ のクエリに対して $k = \lfloor \log_2 (r-l) \rfloor$ とすると $\min (table[k][i], table[k][r-2^k])$ のようにして $\O (1)$ で答えることができる. ここでテーブルの添字は前計算の際にキャッシュに乗りやすいように $k$ , $i$ の順の方が良い.
ちなみに和や xor などもう少し広いクラス(半群をなすもの) に対してもクエリの計算時間 $\O (1)$ を達成するデータ構造を考えることができ, 本アルゴリズムと異なりクエリで呼び出される区間が重ならないことから disjoint sparse table と呼ばれている(参考 noshi さんのブログ).

時間計算量: 構築 $\O (n \log n)$ , クエリ $\O (1)$

コード

template<typename T> class SparseTable {
private:
    int sz;
    vector<int> LogTable;
    vector<vector<T> > Table; //最小値を保持
public:
    SparseTable(const vector<T>& v) : sz((int)v.size()), LogTable(sz + 1){
        for(int i = 2; i < sz + 1; i++){
            LogTable[i] = LogTable[i >> 1] + 1;
        }
        Table.resize(LogTable[sz]+1, vector<T>(sz));
        for(int i = 0; i < sz; i++){
            Table[0][i] = v[i];
        }
        for(int k = 1; (1 << k) <= sz; k++){
            for(int i = 0; i + (1 << k) <= sz; i++){
                Table[k][i] = min(Table[k-1][i], Table[k-1][i + (1 << (k-1))]);
            }
        }
    }
    T query(const int l, const int r){
        const int k = LogTable[r-l];
        return min(Table[k][l], Table[k][r-(1<<k)]);
    }
};

verify 用の問題

Atcooder : Yakiniku Restaurants 提出コード