Iterative implementation of the Segment Tree DS (Basic and non lazy). From: Antii Laaksonen CPHB.

Segment Tree (Basic Structure).cpp

#include <iostream>
using namespace std;
using i64 = long long;

// Memory Required: O(2N)
i64 Tree[i64(2e6) + 1];

i64 N, K, X;

// Puntual Update: O(log N)
void update(i64 idx, i64 val)
{
    idx += N, Tree[idx] = val;
    for (i64 i = idx / 2; i > 0; i /= 2)
        Tree[i] = max(Tree[2 * i], Tree[2 * i + 1]);
}

// Range Query: O(log N)
i64 query(i64 l, i64 r)
{
    l += N, r += N;
    i64 Ans = -1;

    while (l <= r)
    {
        if (l % 2 == 1) Ans = max(Ans, Tree[l++]);
        if (r % 2 == 0) Ans = max(Ans, Tree[r--]);
        l /= 2, r /= 2;
    }

    return Ans;
}

int main()
{
    cin >> N;
    
    // Build: O(N) --------------------------------------

    for (i64 c = 0; c < N; c++)
        cin >> Tree[c + N];

    for (i64 i = N - 1; i >= 1; i--)
        Tree[i] = max(Tree[2 * i], Tree[2 * i + 1]);

    // --------------------------------------------------

    cout << '\n';
    return 0;
}