summaryrefslogtreecommitdiff
path: root/datastructures/sparseTable.cpp
diff options
context:
space:
mode:
authormzuenni <michi.zuendorf@gmail.com>2023-01-10 11:40:09 +0100
committermzuenni <michi.zuendorf@gmail.com>2023-01-10 11:40:09 +0100
commitfd1f2b36e95c03625297b7b8cba3b1a04a0cc0ed (patch)
treeb143619750b90fbfa45a98be9ea56904d1a7129d /datastructures/sparseTable.cpp
parent8faa84ca282d51e9ce4fef535e68325adabcebad (diff)
change whitespaces
Diffstat (limited to 'datastructures/sparseTable.cpp')
-rw-r--r--datastructures/sparseTable.cpp38
1 files changed, 19 insertions, 19 deletions
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp
index 3d11119..40057bd 100644
--- a/datastructures/sparseTable.cpp
+++ b/datastructures/sparseTable.cpp
@@ -1,24 +1,24 @@
struct SparseTable {
- vector<vector<int>> st;
- vector<ll> *a;
+ vector<vector<int>> st;
+ vector<ll> *a;
- bool better(int lidx, int ridx) {
- return a->at(lidx) <= a->at(ridx);
- }
+ bool better(int lidx, int ridx) {
+ return a->at(lidx) <= a->at(ridx);
+ }
- void init(vector<ll> *vec) {
- a = vec;
- st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a)));
- for (int i = 0; i < sz(*a); i++) st[0][i] = i;
- 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)];
- }}}
+ void init(vector<ll> *vec) {
+ a = vec;
+ st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a)));
+ for (int i = 0; i < sz(*a); i++) st[0][i] = i;
+ 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)];
+ }}}
- 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)];
- }
+ 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)];
+ }
}; \ No newline at end of file