From 8054fd7ddbd9533505bc2ced3f6e7f979dca9fb1 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Tue, 2 Jan 2018 21:55:53 +0100 Subject: Removing old RMQ code. --- datastructures/RMQ.cpp | 20 -------------------- 1 file changed, 20 deletions(-) delete mode 100644 datastructures/RMQ.cpp (limited to 'datastructures/RMQ.cpp') diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp deleted file mode 100644 index 0eed967..0000000 --- a/datastructures/RMQ.cpp +++ /dev/null @@ -1,20 +0,0 @@ -vector data(RMQ_SIZE); -vector> rmq(floor(log2(RMQ_SIZE))+1, vector(RMQ_SIZE)); - -// 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++) { - 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]; -}}}} - -// 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); - return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]); -} -- cgit v1.2.3