Минимальное потребление памяти деревом отрезков

Revision ru4, by dmkz, 2019-02-16 21:36:51

UPD. Все, что будет описано ниже, давным давно делает tourist, например, в последней своей посылке.

В древних задачах на сайтах acmp, e-olymp и timus часто ограничения по памяти крайне малы и равны 16 МБ, 32 МБ, 64 МБ. Скорее всего, для современных ограничений в 256 МБ и 512 МБ описанный ниже способ достижения минимального потребления памяти под дерево отрезков не актуален, но все же рассмотрим способ, позволяющий его достичь в реализации сверху-вниз. Будем использовать ровно n - 1 узлов, а вершины пронумеруем в порядке эйлерова обхода:

                    0
         1                  8
   2          5        9         10
3     4    6     7

Тогда, если мы находимся в узле v и это не лист, то у него есть левое и правое поддеревья. Номер левого поддерева равен v + 1, так как в порядке эйлерова обхода мы посетим его сразу после текущего узла. Что касается правого поддерева, то туда мы пойдем только когда посетим корень и все вершины левого поддерева. Количество вершин в поддереве зависит только от длины отрезка, соответствующего узлу дерева.

Будем считать, что если у нас есть отрезок [l, r], то левому поддереву соответствует отрезок [l, m], а правому — [m + 1, r], где m = (l + r) / 2. Тогда длина левого отрезка будет равна m - l + 1, а количество узлов в нем 2·(m - l + 1) - 1.

Окончательно получаем, что для узла v, соответствующего отрезку [l, r], левое поддерево в нумерации в порядке эйлерова обхода будет иметь номер v + 1, а правое — номер v + 2·(m - l + 1), где m = (l + r) / 2 — середина отрезка [l, r].

Tags дерево отрезков

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 Первая редакция (опубликовано)