Sparse Tableを知っていますか？僕は知っています。

Sparse Tableを今更学んだので、メモを兼ねて書きます。

Sparse Tableとは

不変な数列の任意の区間に対する最小値/最大値を、前処理 $O(N\log N)$, クエリごと $O(1)$ で求めるデータ構造です。
数列の値が変わる可能性がある場合はSegmentTreeを使いましょう。SegmentTreeの記事はこちらです。

仕組み

すべての点を始点として、長さが2べきの区間の最小値/最大値を先に求めておきます。これが $O(N\log N)$ の前計算です。
クエリに答えるときは、区間の長さ以下で最大の2べきの値をとり、区間の前側と後ろ側にはめてそれぞれの最小値を求めます。
これで区間全体を覆うことができ、最小値が求まります。

テーブルを構築すると、こんな感じになります。
区間の長さから、それ以下の2べきを求めるのも前計算に含めておくと、クエリごとに $O(1)$ になります。

実装

template<typename T>
class SparseTable {
    T** table;
    int* logtable;
public:
    SparseTable(vector<T> vec) {
        int maxlength = 0;
        while ((1 << (maxlength + 1)) <= vec.size())maxlength++;
        table = new T * [maxlength + 1];
        logtable = new int[vec.size() + 1];
        rep(i, maxlength + 1) {
            table[i] = new T[vec.size()];
            rep(j, vec.size() - (1 << i) + 1) {
                if (i)table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
                else table[i][j] = vec[j];
            }
        }
        for (int i = 2; i <= vec.size(); i++) {
            logtable[i] = logtable[i >> 1] + 1;
        }
    }
    ~SparseTable() {
        rep(i, maxlength) delete[] table[i];
        delete[] table;
        delete[] logtable;
    }
    T query(int l, int r) {
        assert(l < r);
        int length = r - l;
        return min(table[logtable[length]][l], table[logtable[length]][r - (1 << logtable[length])]);
    }
};

かなり雑で可読性が低いです。ごめんなさい。

おわりに

Segment Treeのほうが自分としては書くのが楽ですが、Sparse Tableは定数倍がかなり軽いです。
Sparse Tableもぱっと書けるようにしておくといいかもしれません。（使ったことは、ありません）