**Prerequisites**:

- Standard Segment Tree (https://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:

- $$$A$$$ $$$Pos$$$ $$$newValue$$$: Assign $$$Pos^{th}$$$ element to $$$newValue$$$ ($$$1 \leq Pos \leq N$$$, $$$ 0 \leq newValue \leq 10^9$$$)
- $$$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:

**Link**

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!