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).

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.

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; 
    }

This is a new trick, if any of you are interested. Developed by me and hackerphobia.

Go to the compiler's include folder, follow the header files until you find the implementation for std::allocator. For g++, it is located in /include/c++/{VERSION}/ext/new_allocator.h. After that, find the declaration for a function named allocate. In g++ 11.0, it looks like this:

      _GLIBCXX_NODISCARD _Tp*
      allocate(size_type __n, const void* = static_cast<const void*>(0))
      {
	if (__builtin_expect(__n > this->_M_max_size(), false))
	  {
	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
	    // 3190. allocator::allocate sometimes returns too little storage
	    if (__n > (std::size_t(-1) / sizeof(_Tp)))
	      std::__throw_bad_array_new_length();
	    std::__throw_bad_alloc();
	  }
	}

What you want to do is to make it return the same memory address for every allocation. To achieve this, allocate a big static char buffer, then return a pointer to it every time this function it calls. After modification, the function should look like this:

      _GLIBCXX_NODISCARD _Tp*
      allocate(size_type __n, const void* = static_cast<const void*>(0))
      {
          //Instead of giving each query a private block of memory, make them share the same one and corrupt each other.
          static char buffer[1000000];
          return (_Tp*)(&buffer);
	}

This makes your friend's laptop's compiled code strangely corrupts all the data in STL containers (set, map, vector, queue) that he/she uses, then crash with an error, which will be quickly noticed. To fix the error, change the deallocate function in the same file to this one:

      void
      deallocate(_Tp* __p, size_type __t __attribute__ ((__unused__)))
      {
            //Do nothing, as __p is a pointer to a static buffer!!!
            //If we call operator delete here, the program will crash due to deleting invalid memory.
      }

Ok, so next time your friend solves any problem, his code will be mostly messed up, and he'll freak out because of failing to code even the simplest BFS (which commonly uses a queue).

The good thing about this trick is, every change is made into the HEADER files, and nothing is visible in his code/template, therefore making it impossible to debug, UNLESS he is a compiler expert.

It can help you to pass some problems, provided that your compiler is good and your judge does not have a compile time limit. However, for the sieve problem, the difference is only significant when MaxN >= 1e8, which will often crash the compiler, or if it doesn't, result in an executable too large that linking will fail.

For some other problems where MaxN = 1e4 and you found a O(n^2) solution with O(n) space complexity however, this trick may help you a lot.

1. This trick works in C++14, and needs neither a wrapper class nor a wrapper function:

template<std::size_t N>
struct Sieve 
{
	private:
		bool is_prime[N];
	public:
		constexpr Sieve() : is_prime{0}
		{
			for (int i = 2; i < N; i++) 
			{
				is_prime[i] = true;
			}
			for (int i = 2; i < N; i++)
			{
				if (is_prime[i])
				{
					for (int j = 2 * i; j < N; j += i)
					{
						is_prime[j] = false;
					}
				}
			}
		}
		inline constexpr bool operator[](std::size_t index) const
		{
			return is_prime[index];
		}
};


int main()
{
	//Sieve
	constexpr int MaxN = 1e5;
	Sieve<MaxN> isPrime;

	assert(isPrime[5]);
	//More code here...
}

You can check the assembly here. Starting from line 106, many mov statements are copying bytes to the addresses that should hold prime numbers. Apparently, the constexpr constructor has forced all instances of Sieve to be built in compile time, and the overloading of operator[] allows simple array syntax on the Sieve.

2. This trick may be useful for MaxN <= 1e5, but not higher.

Although compile-time evaluation may theoretically make it possible to compute the Sieve for up to MaxN = 1e9, constexpr evaluation does have a large cost during compile time and also on the binary size. Therefore, setting MaxN to 1e7 or greater may cause the compiler to either crash or report an error, even if -fconstexpr-loop-limit= is set to a large number, while runtime building of a sieve of 1e7 elements is always possible.

Your code C++14 submission uses LCM(int, int) and passes 2 long long arguments. Integer overflow may cause the WA verdict.

Your C++17 submission uses std::LCM(long long, long long), a template instantiation of std::LCM, which is only available since C++17. The built-in LCM function accepts two long long arguments, which does not cause integer overflow.

UPD: AC submission.

Replacing

int lcm(int a, int b){return (a*b)/__gcd(a, b);}

with

ll lcm(ll a, ll b){return (a*b)/__gcd(a, b);}

fixes the problem in C++14.

It's back now again.