SparseTable.java

package data_structures;

// static Range Minimum Query, DP Solution
public class SparseTable {                                          
	  
	int A[], SpT[][];
	
	SparseTable(int[] A) 
	{
		int n = A.length;	this.A = A;
		int k = (int)Math.floor(Math.log(n) / Math.log(2)) + 1;
		SpT = new int[n][k];
		
		for (int i = 0; i < n; i++) 
			SpT[i][0] = i; 					// RMQ of sub array starting at index i and of length 2^0=1
	
		//overall time complexity = O(n log n)
		for (int j = 1; (1<<j) <= n; j++) 				
			for (int i = 0; i + (1<<j) - 1 < n; i++)    
				if (A[SpT[i][j-1]] < A[SpT[i+(1<<(j-1))][j-1]])
					SpT[i][j] = SpT[i][j-1];    		// start at index i of length 2^(j-1)
				else                  					// start at index i+2^(j-1) of length 2^(j-1)
					SpT[i][j] = SpT[i+(1<<(j-1))][j-1];
	 }

	  int query(int i, int j) 
	  {
		  
	    int k = (int)Math.floor(Math.log(j-i+1) / Math.log(2)); // 2^k <= (j-i+1)
	    
	    if (A[SpT[i][k]] <= A[SpT[j-(1<<k)+1][k]]) 
	    	return SpT[i][k];
	    else
	    	return SpT[j-(1<<k)+1][k];
	  } 
}