Wednesday, September 21, 2016

java rmq using sqrt appoach - range minimum query using squre root approach

int[] a;
int bucketSize = (int) Math.ceil(Math.sqrt(a.length));

int[] m = preProcess(a,bucketSize);

               int ans = query(i,j,m,a,bucketSize);

private static int query(int i, int j, int[] m, int[] a, int bucketSize) {
int curr_min = a[i];
if(j - i +1 < 2*bucketSize) {
for(int k=i;k<=j;k++) {
curr_min = Math.min(curr_min, a[k]);
}
return curr_min;
}
int seg_start = (i + bucketSize - 1) / bucketSize;
int seg_end = (j+1)/bucketSize - 1;
curr_min = a[m[seg_start]];
for(int k=seg_start;k<=seg_end;k++)
curr_min = Math.min(curr_min,a[m[k]]);

for(int k=i;k<seg_start*bucketSize;k++)
curr_min = Math.min(curr_min,a[k]);

for(int k=j;k>=(seg_end+1)*bucketSize;k--)
curr_min = Math.min(curr_min,a[k]);

return curr_min;
}

private static int[] process(int[] a, int bucketSize) {
int[] m = new int[(int)Math.ceil(a.length*1.0/bucketSize*1.0)];

int count = 0;
for (int i = 0; count < a.length; i++) {
int min = a[count];
m[i] = count;
for (int j = 0; j < bucketSize && count < a.length; j++) {
if (a[count] < min) {
min = a[count];
m[i] = count;
}
++count;
}
}
return m;
}

No comments:

Blog Archive