summaryrefslogtreecommitdiff
path: root/datastructures/sparseTable.cpp
diff options
context:
space:
mode:
authormzuenni <michi.zuendorf@gmail.com>2023-08-29 00:09:28 +0200
committermzuenni <michi.zuendorf@gmail.com>2023-08-29 00:09:28 +0200
commit4905811a7c635f28827984a999aedacd910f4dc3 (patch)
treed21228d541bb14dc2dc29ffdff2331dfb5ba6b1e /datastructures/sparseTable.cpp
parentf209418070050d4310a19191e3cd771760e5b521 (diff)
consistency
Diffstat (limited to 'datastructures/sparseTable.cpp')
-rw-r--r--datastructures/sparseTable.cpp11
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)]);
}}}