Prerequisites:
- Standard Segment Tree (https://codeforces.net/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 <= 10^5$$$) queries of the following types:
- $$$A$$$ $$$Pos$$$ $$$newValue$$$: Assign $$$Pos^{th}$$$ element to $$$newValue$$$ ($$$1 <= Pos <= N$$$, $$$ 0 <= newValue <= 10^9$$$)
- $$$G$$$ $$$L$$$ $$$R$$$: Get maximum value in range $$$[L, R]$$$ ($$$1 <= L <= R <= n$$$)
We commonly see this problem with $$$N <= 10^5$$$ which can be solved with the Standard Segment Tree (Time Complexity: $$$O(QlogN)$$$). 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 $$$logN$$$ Nodes, so that the number of Nodes that we need is only $$$O(QlogN)$$$ 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 $$$O(QlogN^2)$$$. The better way is to implement each Node with two pointers to its Childs and the complexity is only $$$O(QlogN)$$$.
