1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19

template< typename T > class sparse_table {
private: vector<T> st[20];
public:
	int log(int x) { return 32 - __builtin_clz(x) - 1; }

	sparse_table(vector<T> &A) {
		int N = A.size();
		for (int i = 0; i <= log(N); i++) st[i].resize(N);
		for (int i = 0; i < N; i++) st[0][i] = A[i];
		for (int i = 1; i <= log(N); i++) {
			for (int j = 0; j + (1 << i) <= N; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
		}
	}

	T query(int i, int j) {
		int k = log(j - i + 1);
		return min(st[k][i], st[k][j - (1 << k) + 1]);
	}
};