/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

0 vote309 views1 answer
Vprintf
C++
23 votes304 views2 answers
User input c++
C++
15 votes251 views4 answers
How to make a random number in c++
C++
0 vote256 views1 answer
How to loop through a set of pairs in c++
C++
2 votes313 views2 answers
Resize 2d vector c++
C++
0 vote249 views3 answers
Find the smallest window in a string containing all characters of another string
C++
0 vote271 views1 answer
C++ getline doesn't wait for input
C++
0 vote294 views1 answer
'std::ifstream file' has incomplete type and cannot be defined
C++
0 vote263 views1 answer
Definition of singly linkedlist
C++
1 vote284 views1 answer
How to delete an element in vector pair in cpp
C++