VuaVeNhi's blog

By VuaVeNhi, history, 2 years ago, In English

Prerequisites:

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!

  • Vote: I like it
  • +72
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

Your implementation of the Dynamic Segment Tree has a problem: Memory leak. You allocated children using new Bird():

        if (LeftChild == NULL) LeftChild = new Bird(); 
        if (RightChild == NULL) RightChild = new Bird(); 

but never deleted them.

While in many cases this is not a serious problem, as only one instance of the segment tree is needed and all of its memory is automatically freed after program termination, the memory leak can cause a MLE or RTE for problems where multiple segment trees are used (such as problems with multiple queries,...)

To fix this problem, in your struct Bird, add a destructor, like this:

    ~Bird() // Destructor. Notice the "~" character before the struct name.
    {
        delete LeftChild;
        delete RigthChild;
        LeftChild = NULL; 
        RightChild = NULL; 
    }
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Alternatively, you can put new nodes in a std::deque instead of using new and delete.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    no one cares about memory leaks in CP

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      Having done a bit of CP myself before moving to other software development, I'm aware that some people in CP don't care about memory leaks, and while I explicitly said that in many cases this is not a serious problem, I did state that in problems where multiple segment trees need to be created, such as problems with multiple queries:

      while (t--)
      {
          int n;
          cin >> n;
          Bird tree;
          // do your work here....
      }
      

      A memory leak can cause a MLE, or even worse, an "unexpected" RTE. (Probably some std::bad_alloc somewhere during execution).

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How does using a vector of nodes compare to the pointer implementation in performance and such? In the implementation, you could for example use indexes for the left and right child instead of the left and right pointer.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Performance-wise, a vector of nodes and indexes to elements in that vector should be the best solution.

    As vectors allocate their elements in growing chunks, this should reduce the allocation cost compared to calling new $$$O(NlogN)$$$ times.

»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Chim

»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

best algo

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it really called Bird Tree? I could not find this name anywhere on google

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's not really called anything. Construction is probably called lazy or dynamic.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I had an opportunity to have an interview with the author of this post, and this is what I found out:

    Interview image

    Basically, there are no such thing as "bird tree", even among official Vietnamese documents. The implementation of using pointers, while having appeared in a few Vietnamese competitions, is still really non-standard in Vietnam, so these students thought they have discovered something original. And they claimed: "Khóa em gọi mọi thứ là chim", meaning that their class calls every discovery "bird".

    In the few lines below, they even claim to know something about "Drug Distribution DP" (Quy hoạch động chia ma túy).

    TL;DR: You don't need to worry about finding sources for the "Bird Tree", the name is some made-up term by the author and his classmates.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This implementation is standard to me tbh xd

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

One interesting thing to note is that, if you only have point updates, it is possible to reduce the memory complexity to $$$\mathcal{O}(Q)$$$, but the implementation becomes quite tricky (see the Memory optimization and UPD sections of the this blog).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wtf

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could also get $$$\mathcal{O}(Q)$$$ by splitting in half on even layers and splitting near the query indices on odd layers.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm not sure I understand. Could you please elaborate or send a link describing this trick?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You would need to store the $$$mid$$$ value in each node. Assuming you are on the odd-depth node and need to allocate new children, you would set $$$mid$$$ to either $$$Pos$$$ or $$$Pos-1$$$ (don't create empty subtrees).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

understandable, have a nice day