Sparse Table

typedef long long integer; // change

const int LG = 20, N = 300007; // change

integer op(integer a, integer b) // change
{
    return max(a, b);
}

struct Sparse
{
    int logs[N];
    integer bin[LG][N];
    vector<integer> a;

    int find(int l, int r)  // [l;r)
    {
        int x = logs[r - l];
        return op(bin[x][l], bin[x][r - (1 << x)]);
    }

    void buildBin()
    {
        int n = a.size();
        int cur = 0, x = 1;
        for (int i = 0; i < n + 2; i++)
        {
            if (2 * x == i)
            {
                x *= 2;
                cur++;
            }
            logs[i] = cur;
        }
        for (int i = 0; i < n; i++)
            bin[0][i] = a[i];
        for (int i = 0; i + 1 < LG; i++)
            for (int j = 0; j < n; j++)
                bin[i + 1][j] = op(bin[i][j], bin[i][min(j + (1 << i), n - 1)]);
    }

    Sparce(vector<integer> b)
    {
        a = b;
        buildBin();
    }
};