diff options
Diffstat (limited to 'datastructures/RMQ.cpp')
| -rw-r--r-- | datastructures/RMQ.cpp | 11 |
1 files changed, 4 insertions, 7 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp index 3c3f44c..8e6a33f 100644 --- a/datastructures/RMQ.cpp +++ b/datastructures/RMQ.cpp @@ -1,7 +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)) +// Baut Struktur auf. 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++) { @@ -9,12 +9,9 @@ void initRMQ() { else { int r = l + ss; rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]); - } - } - } -} -//returns index of minimum! [l, r) -//Runtime: O(1) +}}}} + +// Gibt den Index des Minimums im Intervall [l,r) zurück. O(1). int queryRMQ(int l, int r) { if(l >= r) return l; int s = floor(log2(r-l)); r = r - (1 << s); |