Algorithm-and-Data-Structure/DataStructure/SparseTable.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
publicclassSparseTable {
staticintmin (inta, intb) {
returna < b ? a : b;
 }

staticbooleanisValid(intj, inti, intn) {
returnj + (int)Math.pow(2, i) <= n;
 }

staticdoublebaseLog(doublex, doublebase){
returnMath.log(x) / Math.log(base);
 }

staticvoidconstruct(intsparseTable[][], intindexTable[][], introw, intn, intarr[]) {
for (inti = 0; i < n; i++){
sparseTable[0][i] = arr[i];
indexTable[0][i] = i;
 }
for (inti = 1; i <= row; i++) {
for (intj = 0; j < n; j++) {
if (isValid(j, i, n)) {
if (sparseTable[i-1][j] < sparseTable[i-1][j+(int)Math.pow(2, i-1)]) {
sparseTable[i][j] = sparseTable[i-1][j];
indexTable[i][j] = indexTable[i-1][j];
 }else {
sparseTable[i][j] = sparseTable[i-1][j+(int)Math.pow(2, i-1)];
indexTable[i][j] = indexTable[i-1][j+(int)Math.pow(2, i-1)];
 }
 }
 }
 }
 }

staticintminQuery(intsparseTable[][], intl, intr) {
intp = (int)baseLog(r-l+1, 2);
intk = (int)Math.pow(2, p);

returnmin(sparseTable[p][l], sparseTable[p][r-k+1]);
 }

staticintminQueryIndex(intsparseTable[][], intindexTable[][], intl , intr) {
intp = (int)baseLog(r-l+1, 2);
intk = (int)Math.pow(2, p);

if (sparseTable[p][l] < sparseTable[p][r-k+1]) {
returnindexTable[p][l];
 }else {
returnindexTable[p][r-k+1];
 }
 }

publicstaticvoidmain(String[] args) {
intarr[] = {-1, 3, 2, -5, 1, 7, 0};
intn = arr.length;
introw = (int)baseLog(n, 2);
intsparseTable[][] = newint[row + 1][n];
intindexTable[][] = newint[row + 1][n];
construct(sparseTable, indexTable, row, n, arr);

/*
 Sparse Table for Min Query value

 -1 3 2 -5 1 7 0
 -1 2 -5 -5 1 0 x
 -5 -5 -5 -5 x x x

 Index Table for Min Query index

 0 1 2 3 4 5 6
 0 2 3 3 4 6 x
 3 3 3 3 x x x


 for (int i = 0; i <= row; i++) {
 for (int j = 0; j < n; j++) {
 System.out.print(sparseTable[i][j] + " ");
 }
 System.out.println();
 }
 for (int i = 0; i <= row; i++) {
 for (int j = 0; j < n; j++) {
 System.out.print(indexTable[i][j] + " ");
 }
 System.out.println();
 }
 */

// Output: -5
System.out.print("Min Query value is " + minQuery(sparseTable, 0, 6));
// Output: 3 (index)
System.out.println(" and located at index : " + minQueryIndex(sparseTable, indexTable, 0, 6));
 }
}