Декартовы деревья и деревья отрезков (20 марта 2014)

  1. Декартово дерево [кодим]
    1. Декартово дерево по явному ключу [code]
    2. Декартово дерево по неявному ключу [code]
    3. Подсчет функции размер, сумма, минимум на отрезке
    4. reverse отрезка [code]
  2. RSQ, RMQ, LCA, Фенвик
    1. Дерево отрезков, запросы снизу.
      1. Построение за O(n), запрос get за O(logn), запрос change за O(logn) [code]
      2. Памяти 2n [code]
      3. На самом деле время на запрос get O(logLen), Len = R - L + 1
    2. Умеем изменять значение и искать минимум быстрее logn ⇒ умеем сортировать массив быстрее nlogn
    3. Дерево Фенвика для операций a[i] = x, getSum(l, r): n памяти, еще меньше константа [code]
    4. RMQ в Offline за O*(1) [code]
    5. LCA в Offline за O*(1) [code]
    6. LCA в Online двоичными подъемами. [code]
    7. Подсчет функций минимум и сумма на пути дерева двоичными подъемами [code]
    8. Подсчет функций на пути в дереве в Offline за O(дерева отрезков) = O(logn)
    9. Подсчет min на пути в дереве в Offline с помощью СНМ
  3. Корневая эвристика [если останется время]
    1. Отложенные операции (вспомним структуру данных "количество точек в прямоугольнике")
    2. Not read Разбиение на куски постоянного размера (запрос up(L, R, x): на отрезке [L..R] "a[i] = max(a[i], x)", запрос get(L, R): посчитать сумму на отрезке)
    3. Not read Куски изменяющегося размера, split, rebuild (вставка и удаление в массив за √ n )