День 1. Структуры данных (29 декабря)

  1. [Олег] Персистентность
    1. Деревья, массивы, персистентность всего мира, амортизированность убивается
    2. Как писать структуры в чисто функциональном стиле
    3. Декартовы деревья → RBST
    4. Garbage Collector (reference counter)
    5. Персистентность в offline, дерево версий
  2. [Сережа.K] Пополняемые структуры данных
    1. Массив
    2. Точки на плоскости и выпуклая оболочка
    3. Ахо-корасик
  3. [Сережа.K] 2D-деревья.
    1. Дерево отрезков сортированных массивов c запросом за O(log2n).
    2. Ортогональные запросы на плоскости
      1. Решение в offline заметающей прямой за O((m+n)logn)
      2. Решение в online персистентным деревом за O(nlogn) и O(logn) на запрос
      3. Решение в online деревом отрезков сортированных массивов за O(nlogn) и O(log2n) на запрос
      4. Оптимизация 2D дерева отрезков, предподсчет за O(nlogn) и O(logn) на запрос
    3. Дерево отрезков деревьев отрезков.
    4. Дерево Фенвика деревьев Фенвика.
  4. [Сережа.K] Бонус
    1. k-я порядковая статистика на отрезке за O(logn) на запрос