diff options
Diffstat (limited to 'datastructures/RMQ.cpp')
| -rw-r--r-- | datastructures/RMQ.cpp | 10 |
1 files changed, 5 insertions, 5 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp index b38b838..8e5cc3f 100644 --- a/datastructures/RMQ.cpp +++ b/datastructures/RMQ.cpp @@ -6,22 +6,22 @@ int select(int a, int b) { } void build() { - for(int i = 0, s = 1, ss = 1; s <= values.size(); ss=s, s*=2, i++) { - for(int l = 0; l + s <= values.size(); l++) { + for(int i = 0, s = 1, ss = 1; s <= sz(values); ss=s, s*=2, i++) { + for(int l = 0; l + s <= sz(values); l++) { if(i == 0) rmq[0][l] = l; else { int r = l + ss; rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]); }}}} -void init(vector<int>& v) { +void init(const vector<int>& v) { values = v; - rmq = vector<vector<int>>(floor(log2(values.size()))+1, vector<int>(values.size())); + rmq = vector<vector<int>>(__lg(sz(values))+1, vector<int>(sz(values))); build(); } int query(int l, int r) { if(l >= r) return l; - int s = floor(log2(r-l)); r = r - (1 << s); + int s = __lg(r-l); r = r - (1 << s); return select(rmq[s][l],rmq[s][r]); }
\ No newline at end of file |