Minimum memory consumption by the segment tree

Revision en3, by dmkz, 2019-02-16 12:00:11

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

Tags segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru4 Russian dmkz 2019-02-16 21:36:51 99
en4 English dmkz 2019-02-16 21:36:23 110
en3 English dmkz 2019-02-16 12:00:11 211 Tiny change: 'eady used [user:tou' -> 'eady used by [user:tou'
ru3 Russian dmkz 2019-02-16 11:56:45 186 Мелкая правка: 'UPD. Все, что' -> '**UPD**. Все, что'
en2 English dmkz 2019-02-16 11:46:35 8 Tiny change: 'dash; the number $ v + 2 \' -> 'dash; the vertex $ v + 2 \'
en1 English dmkz 2019-02-16 11:43:59 1865 Initial revision for English translation
ru2 Russian dmkz 2019-02-16 11:21:46 12 Мелкая правка: 'ько когда мы посетим все верши' -> 'ько когда посетим корень и все верши'
ru1 Russian dmkz 2019-02-16 11:19:57 1669 Первая редакция (опубликовано)