diff options
| -rw-r--r-- | datastructures/RMQ.cpp | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp new file mode 100644 index 0000000..899db15 --- /dev/null +++ b/datastructures/RMQ.cpp @@ -0,0 +1,20 @@ +vector<int> data(RMQ_SIZE); +vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE)); + +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++) { + if(i == 0) rmq[0][l] = l; + 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! [a, b) +int queryRMQ(int l, int r) { + if(l >= r) return l; + int s = floor(log2(r-l)); r = r - (1 << s); + return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]); +} |