diff options
Diffstat (limited to 'datastructures/sparseTable.cpp')
| -rw-r--r-- | datastructures/sparseTable.cpp | 11 |
1 files changed, 6 insertions, 5 deletions
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp index 61a6802..7578695 100644 --- a/datastructures/sparseTable.cpp +++ b/datastructures/sparseTable.cpp @@ -3,15 +3,16 @@ struct SparseTable { vector<ll> *a; int better(int lidx, int ridx) { - return a->at(lidx) <= a->at(ridx) ? lidx : ridx; + return a[lidx] <= a[ridx] ? lidx : ridx; } void init(vector<ll> *vec) { - a = vec; - st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a))); + int n = sz(*vec); + a = vec->data(); + st.assign(__lg(n) + 1, vector<int>(n)); iota(all(st[0]), 0); - for (int j = 0; (2 << j) <= sz(*a); j++) { - for (int i = 0; i + (2 << j) <= sz(*a); i++) { + 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)]); }}} |