Consulta para RMQ usando a decomposição do SQRT
int query(int l, int r)
{
int LB = l/Blk; //Blk = block size
int RB = r/Blk;
int minimum = INT_MAX;
if(LB == RB) {
for(int i=l; i<=r; i++) {
minimum = min(minimum, arr[i]);
}
}
else {
for(int i=l; i<Blk*(LB+1); i++) minimum = min(minimum, arr[i]);
for(int i=LB+1; i<RB; i++) minimum = min(minimum, seg[i]);
for(int i=RB*Blk; i<=r; i++) minimum = min(minimum, arr[i]);
}
return min;
}
Wandering Wolverine