From 1f51a4c86787f734e82036f990b28958b188825d Mon Sep 17 00:00:00 2001 From: Noobie99 Date: Tue, 28 Feb 2023 18:41:44 +0100 Subject: simplified sparse table --- datastructures/sparseTable.cpp | 14 ++++++-------- 1 file changed, 6 insertions(+), 8 deletions(-) (limited to 'datastructures') diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp index cf21e9a..719fd73 100644 --- a/datastructures/sparseTable.cpp +++ b/datastructures/sparseTable.cpp @@ -2,23 +2,21 @@ struct SparseTable { vector> st; vector *a; - bool better(int lidx, int ridx) { - return a->at(lidx) <= a->at(ridx); + int better(int lidx, int ridx) { + return a->at(lidx) <= a->at(ridx) ? lidx : ridx; } void init(vector *vec) { a = vec; st.assign(__lg(sz(*a)) + 1, vector(sz(*a))); - for (int i = 0; i < sz(*a); i++) st[0][i] = i; + iota(all(st[0]), 0); for (int j = 0; (2 << j) <= sz(*a); j++) { for (int i = 0; i + (2 << j) <= sz(*a); i++) { - st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]) - ? st[j][i] : st[j][i + (1 << j)]; + st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]); }}} int queryIdempotent(int l, int r) { int j = __lg(r - l); //31 - builtin_clz(r - l); - return better(st[j][l] , st[j][r - (1 << j)]) - ? st[j][l] : st[j][r - (1 << j)]; + return better(st[j][l] , st[j][r - (1 << j)]); } -}; +} -- cgit v1.2.3