query for rmq using sqrt decomposition

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class RMQ {
private:
    vector<int> arr;
    vector<int> block_min;
    int block_size;

public:
    RMQ(const vector<int>& input) {
        arr = input;
        int n = arr.size();
        block_size = static_cast<int>(sqrt(n)) + 1;
        block_min.resize(block_size, INT_MAX);

        for (int i = 0; i < n; ++i)
            block_min[i / block_size] = min(block_min[i / block_size], arr[i]);
    }

    int query(int l, int r) {
        int min_val = INT_MAX;

        while (l <= r && l % block_size != 0) {
            min_val = min(min_val, arr[l]);
            ++l;
        }

        while (l + block_size - 1 <= r) {
            min_val = min(min_val, block_min[l / block_size]);
            l += block_size;
        }

        while (l <= r) {
            min_val = min(min_val, arr[l]);
            ++l;
        }

        return min_val;
    }
};

int main() {
    vector<int> input = {7, 2, 3, 0, 5, 10, 3, 12};
    RMQ rmq(input);

    cout << "Minimum in range [1, 5]: " << rmq.query(1, 5) << endl;
    cout << "Minimum in range [2, 7]: " << rmq.query(2, 7) << endl;
    cout << "Minimum in range [0, 3]: " << rmq.query(0, 3) << endl;

    return 0;
}