Корневая оптимизация (11 декабря 2014)

  1. Частичные суммы и частичные минимумы на меняющемся массиве
    1. RSQ [O(n), O(1)] = Partial Sums, RMQ [O(nlogn), O(1)] = Sparse Table
    2. RSQ [O(1), O(n)] = for, RMQ [O(1), O(n)] = for
    3. RSQ [O(1), O(n1/2)], [O(1), O((nlogn)1/2)]
    4. RSQ [O(n1/2), O(n1/2)], [O(n1/2logn), O(1)]
  2. Разбор задачи "приказы" корневой оптимизацией
  3. Кодим
    1. Сумма на отрезке и присвоение на отрезке
      1. Решение за квадрат [code]
      2. Решение корневой [code]
      3. Решение корневой, оптимизируем код [code]
    2. По таблице инверсий восстановить перестановку [code]
  4. Отложенные операции
    1. На примере задачи про сумму на отрезке на меняющемся массиве
    2. Необычная задача: множество точек, находить самую дальнюю по направлению