/C++/Query for rmq using sqrt decomposition

Query for rmq using sqrt decomposition

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;
}

Source: youtube.com

Similar codes

3 votes201 views2 answers
Cpp map insert
C++
0 vote170 views1 answer
C++ sorting and keeping track of indexes
C++
19 votes163 views2 answers
Files c++
C++
4 votes176 views2 answers
C++ initialize a vector
C++
0 vote231 views1 answer
How to initialize 2d array with values c++
C++
0 vote178 views1 answer
Stringstream stream number to string
C++
0 vote178 views1 answer
Generate random string in c++
C++
0 vote173 views1 answer
Phi function (n log (log(n)))
C++
2 votes177 views2 answers
C++ while true loop
C++
0 vote160 views1 answer
Not c++
C++