Segment tree

#define l(n) (2 * n)
#define r(n) (2 * n + 1)
#define f(x, y) max(x, y)
#define def INT_MIN

int n;
vector<int> st;

void build(vector<int>& T)
{
    for (n = 1; n < T.size(); n *= 2);
    st.resize(n * 2, 0);

    for (int i = n; i < 2 * n; i++)
        st[i] = T[i - n];
    for (int i = n - 1; i > 0; i--)
        st[i] = f(st[l(i)], st[r(i)]);
}

void update(int pos, int val)
{
    st[pos += n] = val;
    while ((pos /= 2) > 0)
        st[pos] = f(st[l(pos)], st[r(pos)]);
}

int query_rec(int l, int r, int n, int lhs, int rhs)
{
    if (lhs > r || rhs < l)   return def;
    if (lhs >= l && rhs <= r) return st[n];
    int m = lhs + (rhs - lhs) / 2;
    int res = f(query_rec(l, r, l(n), lhs, m), query_rec(l, r, r(n), m + 1, rhs));
    return res;
}

inline int query(int l, int r)
{
    return query_rec(l, r, 1, 0, n - 1);
}