Skip to content

Instantly share code, notes, and snippets.

@ddrone
Created June 22, 2012 23:06
Show Gist options
  • Save ddrone/2975702 to your computer and use it in GitHub Desktop.
Save ddrone/2975702 to your computer and use it in GitHub Desktop.
Implementation of online static RMQ-problem with O(N) preprocessing time and O(1) query time
// This code is in public domain.
// Written by Andrew Shulayev, 2012
import java.util.*;
import java.io.*;
// current version doesn't work properly
public class LinearTimeRMQ
{
// cartesian tree class declaration
static class Node
{
public int key, priority;
private Node left, right, parent;
public Node(int key, int priority)
{
this.key = key;
this.priority = priority;
}
public void setLeft(Node left)
{
assert left != this;
this.left = left;
if (left != null)
left.parent = this;
}
public void setRight(Node right)
{
assert right != this;
this.right = right;
if (right != null)
right.parent = this;
}
}
// RMQ -> LCA reduction
// linear-time construction of cartesian tree from integer array
// keys are array indices, priorities are values
static public Node buildTreeFromArray(int[] array)
{
int n = array.length;
assert n > 0;
Node tree = new Node(0, array[0]);
for (int i = 1; i < n; i++)
{
Node node = new Node(i, array[i]);
while (tree.parent != null && tree.priority > array[i])
{
tree = tree.parent;
}
if (tree.priority > array[i])
{
node.setLeft(tree);
}
else
{
node.setLeft(tree.right);
tree.setRight(node);
}
tree = node;
}
while (tree.parent != null)
{
tree = tree.parent;
}
return tree;
}
// following procedure gives index -> node correspondence
// for cartesian tree built by previous procedure
static public void fillIndexToNode(Node[] array, Node node)
{
if (node == null)
return;
array[node.key] = node;
fillIndexToNode(array, node.left);
fillIndexToNode(array, node.right);
}
// LCA -> ±1 RMQ reduction
static public int fillEulerWalk(int[] depths, int[] indices, int[] needValues, Node node, int start, int depth)
{
assert node != null;
indices[node.key] = start;
depths[start] = depth;
needValues[start] = node.priority;
if (node.left != null)
{
start = fillEulerWalk(depths, indices, needValues, node.left, start + 1, depth + 1);
depths[start] = depth;
needValues[start] = node.priority;
}
if (node.right != null)
{
start = fillEulerWalk(depths, indices, needValues, node.right, start + 1, depth + 1);
depths[start] = depth;
needValues[start] = node.priority;
}
return start + 1;
}
// sparse table construction
// table[i][j] stores min(array[i; i + 2^j))
static public int[][] buildSparseTable(int[] array)
{
int h = 0, s = 1;
int n = array.length;
while (s < array.length)
{
s *= 2;
h++;
}
// h = ceil(log_2(n))
int[][] result = new int[n][h + 1];
for (int i = 0; i < n; i++)
result[i][0] = array[i];
s = 1;
for (int j = 1; j <= h; j++)
{
for (int i = 0; i < n; i++)
{
result[i][j] = result[i][j - 1];
if (i + s < n)
result[i][j] = Math.min(result[i][j], result[i + s][j - 1]);
}
s *= 2;
}
return result;
}
// sparse table query
// returns min(array[l; r))
// logfloor and floorpow passed as parameters because it's computation
// takes logarithmic time. Using precomputed values, we get constant
// working time for query.
static public int sparseTableQuery(int[][] table, int[] logfloor, int[] floorpow, int l, int r)
{
int h = logfloor[r - l];
return Math.min(table[l][h], table[r - floorpow[r - l]][h]);
}
static public int[][][] build4RussiansTable(int n)
{
assert n > 0;
int[][][] result = new int[1 << n][n][n + 1];
for (int mask = 0; mask < (1 << (n - 1)); mask++)
{
int[] array = new int[n];
array[0] = 0;
for (int i = 1; i < n; i++)
{
array[i] = array[i - 1];
if (((1 << (i - 1)) & mask) > 0)
array[i] += 1;
else
array[i] -= 1;
}
for (int i = 0; i < n; i++)
result[mask][i][i + 1] = array[i];
for (int l = 2; l <= n; l++)
for (int i = 0; i + l <= n; i++)
result[mask][i][i + l] = Math.min(result[mask][i][i + l - 1], array[i + l - 1]);
}
return result;
}
int[] array; // done
int[][] sparse; // done
int[] logfloor; // done
int[] floorpow; // done
int blocksize; // done
int[][][] rus4; // done
int[] depths; // done
int[] indices; // done
Node tree;
int[] blockmin;
Node[] indexToNode;
int[] needValues;
public LinearTimeRMQ(int[] array)
{
this.array = array;
tree = buildTreeFromArray(array);
int n = array.length;
depths = new int[2 * n - 1];
needValues = new int[2 * n - 1];
indices = new int[n];
fillEulerWalk(depths, indices, needValues, tree, 0, 0);
indexToNode = new Node[n];
fillIndexToNode(indexToNode, tree);
n = 2 * n - 1;
int h = 0, s = 1;
while (s < n)
{
h += 1;
s *= 2;
}
blocksize = (h + 1) / 2;
blockmin = new int[(n - 1) / blocksize + 1];
for (int i = 0; i < n; i++)
{
//System.out.printf("i = %d, depths.length = %d\n", i, depths.length);
int block = i / blocksize;
if (i % blocksize == 0)
blockmin[block] = depths[i];
else
blockmin[block] = Math.min(blockmin[block], depths[i]);
}
sparse = buildSparseTable(blockmin);
int m = blockmin.length + 1;
logfloor = new int[m];
floorpow = new int[m];
logfloor[1] = 0;
floorpow[1] = 1;
for (int i = 2; i < m; i++)
{
logfloor[i] = logfloor[i / 2] + 1;
floorpow[i] = floorpow[i / 2] * 2;
}
rus4 = build4RussiansTable(blocksize);
}
public int getRMQ(int left, int right)
{
left = indices[left];
right = indices[right - 1];
if (right < left)
{
int temp = right;
right = left;
left = temp;
}
if (left == right)
{
return needValues[left];
}
//System.out.printf("left = %d, right = %d\n", left, right);
int left_block = (left / blocksize);
int right_block = (right / blocksize);
int between_blocks = Integer.MAX_VALUE;
if (left_block + 1 < right_block)
between_blocks = sparseTableQuery(sparse, logfloor, floorpow, left_block + 1, right_block);
int left_mask = 0;
for (int k = 1; k < blocksize; k++)
left_mask = left_mask * 2 + (depths[left_block * blocksize + k] - depths[left_block * blocksize + k - 1] + 1) / 2;
int right_mask = 0;
for (int k = 1; k < blocksize; k++)
right_mask = right_mask * 2 + (depths[right_block * blocksize + k] - depths[right_block * blocksize + k - 1] + 1) / 2;
int left_result = rus4[left_mask][left - left_block * blocksize][blocksize] + depths[left_block * blocksize];
int right_result = rus4[right_mask][0][right - right_block * blocksize + 1] + depths[right_block * blocksize];
//System.out.printf("%d, %d, %d\n", between_blocks, left_result, right_result);
return needValues[Math.min(between_blocks, Math.min(left_result, right_result))];
}
public void testRMQ(int l, int r, PrintStream out)
{
int ans = array[l];
for (int i = l + 1; i < r; i++)
{
ans = Math.min(ans, array[i]);
}
int result = getRMQ(l, r);
if (ans == result)
out.printf("ok, rmq(%d, %d) = %d\n", l, r, ans);
else
out.printf("wa, rmq(%d, %d) = %d, expected %d\n", l, r, result, ans);
}
// debug output: print tree to stream
static void printTree(Node tree, String spaces, PrintStream stream)
{
if (tree == null)
return;
stream.print(spaces);
stream.printf("%d, %d\n", tree.key, tree.priority);
printTree(tree.left, spaces + " ", stream);
printTree(tree.right, spaces + " ", stream);
}
public static void main(String[] args) throws IOException
{
int[] array = new int[] { 4, 2, 1, 5, 7, 9, -1, -3 };
int n = array.length;
Node tree = buildTreeFromArray(array);
Node[] indexToNode = new Node[n];
fillIndexToNode(indexToNode, tree);
printTree(tree, "", System.out);
System.out.println(Arrays.toString(array));
LinearTimeRMQ rmq = new LinearTimeRMQ(array);
System.out.println(rmq.blocksize);
System.out.println(Arrays.toString(rmq.blockmin));
System.out.println(Arrays.toString(rmq.depths));
System.out.println();
for (int[] row : rmq.sparse)
{
System.out.println(Arrays.toString(row));
}
System.out.println();
for (int[][] row : rmq.rus4)
{
System.out.println(Arrays.deepToString(row));
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
rmq.testRMQ(i, j, System.out);
}
}
return;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment