Блог пользователя dmkz

Автор dmkz, история, 6 лет назад, По-русски

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

  • Проголосовать: нравится
  • +141
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://codeforces.me/blog/entry/18051 — same tree with different traversal

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Simple and great idea! But I didn't get the last line. which is r - l + 2 if l and r have same parity and r - l + 1 otherwise.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Looks like I forgot to multiply on 2 after division. I mean that we need to add leftLen to v, but leftLen is the half of rootLen = r - l + 1 after division. Correct formula is v + (r - l + 1 + 1) / 2 * 2 = v + (r - l) / 2 * 2 + 2, so with midpoint formula looks more easy, I will remove last abstract

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

This idea is mostly based on cache locality rather than memory consumption.

I've seen this while studying cache-oblivious data structures. Such tree works significantly faster than most others, because it is cache-friendly. (subtree of vertex v contains of some interval [l..r])

Had some benchmarks made for such tree, but can't find them right now.

  • »
    »
    6 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry, can't reproduce speed up from cache optimizations. Tried on problem with 1.000.000 items and queries increment values on segment by constant and get maximal value on segment. 0.7 s vs 0.7 s for both orders: Euler Tour order, simple order

    Can you, please, found experiments what you did?