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もぱっと書けるようにしておくといいかもしれません。（使ったことは、ありません）