Bird Tree

// Written by BacHoCuuPikachu
#include <bits/stdc++.h>

using namespace std;

struct Bird
{
    int Value; // Minimum value of a segment
    Bird *LeftChild, *RightChild; // Pointers to left child and right child

    Bird() // Constructor
    {
        Value = 0;
        LeftChild = NULL;
        RightChild = NULL;
    }

    void BirdLay() // Construct Childs
    {
        if (LeftChild == NULL) LeftChild = new Bird();
        if (RightChild == NULL) RightChild = new Bird();
    }
};

Bird* Root = new Bird(); // The first Node that manage [1, N]

void BirdPerch(Bird *Current, int curL, int curR, int Pos, int newValue)
{
    if (curL > Pos || curR < Pos) { // Pos is not in range [curL, curR]
        return;
    }

    if (curL == curR) { // Current is the Node that manage only Posth element
        Current -> Value = newValue;
        return;
    }

    int mid = (curL + curR) / 2;
    Current -> BirdLay();
    BirdPerch(Current -> LeftChild, curL, mid, Pos, newValue);
    BirdPerch(Current -> RightChild, mid + 1, curR, Pos, newValue);
    Current -> Value = max(Current -> LeftChild -> Value,
                           Current -> RightChild -> Value);
}

int BirdFly(Bird *Current, int curL, int curR, int L, int R)
{
    if (curL > R || curR < L) { // [curL, curR] doesn't intersect with [L, R]
        return 0;
    }

    if (L <= curL && curR <= R) { // [curL, curR] is inside [L, R]
        return Current -> Value;
    }

    int mid = (curL + curR) / 2;
    Current -> BirdLay();
    return max(BirdFly(Current -> LeftChild, curL, mid, L, R),
               BirdFly(Current -> RightChild, mid + 1, curR, L, R));
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;

    char Type;
    int Pos, newValue, L, R;

    while (Q--) {
        cin >> Type;
        if (Type == 'A') {
            cin >> Pos >> newValue;
            BirdPerch(Root, 1, N, Pos, newValue);
        }
        else { // Type == 'G'
            cin >> L >> R;
            cout << BirdFly(Root, 1, N, L, R) << '\n';
        }
    }
}