content/datastructures/sparseTable.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct SparseTable {
	vector<vector<int>> st;
	ll *a;

	int better(int lidx, int ridx) {
		return a[lidx] <= a[ridx] ? lidx : ridx;
	}

	void init(vector<ll> &vec) {
		int n = ssize(vec);
		a = vec.data();
		st.assign(__lg(n) + 1, vector<int>(n));
		iota(begin(st[0]), end(st[0]), 0);
		for (int j = 0; (2 << j) <= n; j++) {
			for (int i = 0; i + (2 << j) <= n; i++) {
				st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]);
	}}}

	int query(int l, int r) {
		if (r <= l) return -1;
		int j = __lg(r - l); //31 - builtin_clz(r - l);
		return better(st[j][l] , st[j][r - (1 << j)]);
	}
};