Что: Лекция
Когда: Пятница, 02 декабря 2016, 18:30–20:00
Где: Таймс, 4 этаж

Описание

  • Дерево отрезков с операциями сверху

    • Построение за O(n), изменение в точке, запрос на отрезке
    • Модификация на отрезке
    • Динамическое дерево отрезков (координаты до \(10^9\))
  • Идея сканирующей прямой. Обработка событий. На примере задачи: найти самую длинную цепочку точек, возрастающую по обеим координатам.

  • Дерево отрезков с операциями снизу

  • Дерево Фенвика для функции на префиксе