Prerequisites:

• Standard Segment Tree (https://mirror.codeforces.com/blog/entry/15890)
• Pointers (https://www.w3schools.com/cpp/cpp_pointers.asp)

Problem statement:

Given an array with $$$N$$$ zeros, your task is to process $$$Q$$$ ($$$Q \leq 10^5$$$) queries of the following types:

1. $$$A$$$ $$$Pos$$$ $$$newValue$$$: Assign $$$Pos^{th}$$$ element to $$$newValue$$$ ($$$1 \leq Pos \leq N$$$, $$$ 0 \leq newValue \leq 10^9$$$)
2. $$$G$$$ $$$L$$$ $$$R$$$: Get maximum value in range $$$[L, R]$$$ ($$$1 \leq L \leq R \leq n$$$)

We commonly see this problem with $$$N \leq 10^5$$$ which can be solved with the Standard Segment Tree (Time Complexity: $$$\mathcal{O}(Q\log{}N)$$$). But if $$$N$$$ is up to $$$10^9$$$, the tree requires the size of $$$4 * 10^9$$$ which is impossible. We still can solve this by using the Standard Segment Tree and process the queries offline (mapping all the $$$Pos$$$(s) in the queries of first type and using binary search). However, there is another way to solve by using Dynamic Segment Tree.

Dynamic Segment Tree (also called Bird Tree — “Cây Chim” — in Vietnam) is a Segment Tree but only has necessary Nodes. We see that each query only need access to $$$\log{}N$$$ Nodes, so that the number of Nodes that we need is only $$$Q\log{}N$$$ Nodes which is possible.

We can implement as Standard Segment Tree but instead of using array to build the tree, we use map but the complexity is $$$\mathcal{O}(Q\log{}N\log{}(Q\log{}N))$$$. The better way is to implement each Node with two pointers to its Children and the complexity is only $$$\mathcal{O}(Q\log{}N)$$$.

Implementation:

• Firstly, the Tree’s Node is the struct with value and pointers to its Children:

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(); 
    } 
}; 

• A function to update $$$Pos^{th}$$$ element to $$$newValue$$$:

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); 
} 

• A function to get maximum value in range $$$[L, R]$$$:

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)); 
} 

With this all, we can finally solve the problem in $$$\mathcal{O}(Q\log{}N)$$$.

Here is my source code for the problem:

In conclusion, though the complexity is $$$\mathcal{O}(Q\log{}N)$$$, using pointers makes the code run slower. So I still recommend using Standard Segment Tree instead of this. You should only use Bird Tree when there is no other choice.

Thanks for reading! Have a lovely day!