diff options
| author | Paul Jungeblut <paul.jungeblut@gmail.com> | 2015-12-03 01:13:09 +0100 |
|---|---|---|
| committer | Paul Jungeblut <paul.jungeblut@gmail.com> | 2015-12-03 01:13:09 +0100 |
| commit | 460c5be29f39c62cb1842772ab305308a05b79ff (patch) | |
| tree | c141c1b5c5eeb8b5670d0a405f202772ca48af48 /datastructures/RMQ.cpp | |
| parent | 53e7f12d828bb94c05d2b6c4e04d61de9482c426 (diff) | |
| parent | fa3508ac4b96b39435ab8671412126fefc59bea8 (diff) | |
Merge in Fenwick Tree
Diffstat (limited to 'datastructures/RMQ.cpp')
| -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); |