Implement Dynamic Segment Tree Using Pointers

Правка en1, от VuaVeNhi, 2022-09-14 03:28:08

Prerequisites:

Problem statement:

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

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

Теги data structures, bird tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский VuaVeNhi 2022-09-14 04:26:18 2 (published)
en2 Английский VuaVeNhi 2022-09-14 04:22:14 2516 Tiny change: ' the $Pos$s in the qu' -> ' the $Pos${s} in the qu'
en1 Английский VuaVeNhi 2022-09-14 03:28:08 1519 Initial revision (saved to drafts)