-
Notifications
You must be signed in to change notification settings - Fork 0
/
SparseTable.java
36 lines (28 loc) · 1.02 KB
/
SparseTable.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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];
}
}