UPD. Everything that will be described below is already used by tourist for a long time, for example, in his last submission.

In ancient problems on russian competitive programming cites, memory constraints are often extremely small and equal to 16 MB, 32 MB, 64 MB. Most likely, for modern memory constraints of 256 MB and 512 MB, the method described below for achieving the minimum memory consumption for the segment tree is not relevant, but still consider a method that allows it to be achieved in the top-down implementation. We will use exactly 2·n - 1 nodes, and number the vertices in the Euler Tour order:

                    0
         1                  8
   2          5        9         10
3     4    6     7

Then, if we are in the node v and this is not a leaf, then it has left and right subtrees. The vertex of the left subtree is v + 1, because, in the order of the Euler Tour, we will visit it immediately after the current node. As for the right subtree, we will go there only when we visit the current vertex and all the vertices of the left subtree. The number of vertices in a subtree depends only on the length of the segment corresponding to the tree node.

We assume that if we have a segment [l, r], then the left subtree corresponds to the segment [l, m], and the right one — [m + 1, r], where m = (l + r) / 2. Then the length of the left segment will be equal to m - l + 1, and the number of nodes in it is 2·(m - l + 1) - 1.

Finally, we find that for the node v corresponding to the segment [l, r], the left subtree in the numbering in the Euler Tour order will be v + 1, and the right one — the vertex v + 2·(m - l + 1), where m = (l + r) / 2 — the midpoint of the segment [l, r].

Additionally it is not difficult to see that 2·(m - l + 1) = (r - l + 2) / 2 = (r - l) / 2 + 1