diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/RMQ.cpp | 2 |
1 files changed, 2 insertions, 0 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp index 9047b33..3c3f44c 100644 --- a/datastructures/RMQ.cpp +++ b/datastructures/RMQ.cpp @@ -1,6 +1,7 @@ vector<int> data(RMQ_SIZE); vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE)); +//Runtime: O(n*log(n)) void initRMQ() { for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) { for(int l = 0; l + s <= RMQ_SIZE; l++) { @@ -13,6 +14,7 @@ void initRMQ() { } } //returns index of minimum! [l, r) +//Runtime: O(1) int queryRMQ(int l, int r) { if(l >= r) return l; int s = floor(log2(r-l)); r = r - (1 << s); |