=^_^= Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 06 - Деревья отрезков

Note: Звездочкой отмечены темы, на которые на лекции времени не хватило.

Краткий план лекции на тему "Деревья отрезков"

  1. Дерево отрезков
  2. Модификация на отрезке
  3. Динамическое дерево отрезков
  4. Задачи на дерево отрезков
  5. Метод сканирующей прямой
  6. 2D дерево отрезков
  7. 2D дерево отрезков, работающее online за O(logn)

Полный план лекции

  1. Дерево отрезков
    1. Собственно структура, округление до 2^k
    2. Построение за O(n)
    3. Реализация снизу, ровно 2n памяти
    4. Реализация сверху
    5. Запросы [L..R] += x, [L..R] = x (сверху)
  2. Динамическое дерево отрезков
    1. Моделирование BSTree с помощью дерева отрезков для x = 0..10^5
    2. x = 0..10^9 => сжатие координат
    3. Без сжатия координат = динамическое дерево : O(m*logM) памяти и времени
    4. Оптимизация1 : отсекаемся, когда вершина содержит 1 элемент
    5. * Оптимизация2 : tree.R = tree.L + 1
    6. * Оптимизация3 : сжатое дерево => O(n) памяти
  3. Задачи на дерево отрезков
    1. Запросы [L..R] = c и для каждого цвета в конце сказать, сколько его [при сжатии координат [L,R] --> [L,R+1)]
    2. Запросы [L..R] = c и по ходу отвечать, сколько различных отрезков
    3. Есть множество чисел <= 10^5. Add, Del, GetMin, DelMin (моделируем кучу, ищем позицию min-а)
    4. Дан массив за 10^5 чисел <= 10^9. GetMin, DelMin [заменям a[i] на inf]
    5. Add, Del, Переход к минимальному числу >= x.
    6. Дана строка, удаляются по очереди все символы и даны запросы-отрезки, нужно после каждого удаления символа выводить список только что удаленных отрезков.
      1. Посл-ть удалений дана Offline => max по времени на отрезке
      2. Online => Разделяем каждый отрезок на O(logN) частей (вершин д.о.), а свежеудаленные вершины д.о. находим за O(logN)
  4. Метод сканирующей прямой
    1. 2D. Max по длине посл-ть вложенных точек.
    2. Max по вложенности множество отрезков [отрезок = точка]
    3. Точка, покрытая Max числом прямоугольников
    4. Запрос на прямоугольнике в Offline [прямоугольник = полоска - полоска]
    5. Покрыть прямоугольником WxH множество точек Max по сумме весов
  5. 2D дерево отрезков
    1. Предподсчет = O(nlogn). Запрос на прямоугольнике = O((logn)^2)
    2. Значение в точке можно менять.
    3. Если дерево сделать динамическим, сами точки можно менять.
    4. Статический случай (значения в точках не меняются) => Запрос за O(logn)
    5. Предподсчет для запроса за O(logn) [метод двух указателей]
    6. Применение этой идеи к функции min [min на отрезке за O(loglogn), O(log*n), O(1)]
    7. Модификация на прямоугольнике за O((logn)^2) [потом за O(nlogn) считаем значение во всех точках]