### VuaVeNhi's blog

By VuaVeNhi, history, 20 months ago,

### 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!

• +72