Блог пользователя I_love_myself

Автор I_love_myself, 7 лет назад, По-русски

Всем привет, мне так понравилось как растет мой вклад я вижу, что вам понравился разбор в предыдущем посте, поэтому я решил периодически рассказывать о разных задачах, во многом, с применением не очень сложных структур данных.
Сегодня я рассажу вам об оптимизациях дерева отрезков и декартовых деревьях(все вещи аналогичны ДО), позволяющих скинуть лишний логарифм в асимптотике, также разберу одну подзадачу, позволяющую решать кучу задач.
Будут разобраны:
1. Двоичный спуск
2. Fractional cascading
3. Задачи с удалением и добавлением элементов

1) Двоичный спуск
Пусть вам надо найти элемент, начиная с которого сумма больше K, а вы очень упорный и не любите частичные суммы, зато хлебом вас не корми, дай дерево отрезков написать! А всё это надо сделать за log!! Как быть? На помощь приходят двоичные спуски!
Пусть вы знаете сумму в левом поддереве, тогда если она больше K0, то переходим в него, иначе — в правое поддерево с K1 = K0 — sum(left).

В целом, двоичные спуски требуются, если в какой-то задачке вы хотите бинпоиском узнавать что-то через ДО: аналогичной идеей вы каждый раз понимаете в какое поддерево нужно спуститься.
Сложность:

2) Fractional cascading
К сожалению, на русскоязычных ресурсах об этом ничего нет(UPD: на e-maxx, говорят, есть), хотя это моя сама любимая оптимизация, которая мне ни разу не пригодилась, но делает крутые вещи :)
Итак, задача: найти k-тый элемент на отрезке [L; R], если бы отрезок был отсортирован — это назывется k-тая статистика на отрезке. (Бонус: придумайте как решать эту задачу персистентным ДО)
Ну а в задаче такие ограничения, что требуется на запрос.

Для начала дадим понятие MergeSortTree — это дерево отрезков, в вершине которого хранится отсортированный массив из 2-х отсортированных массивов его сыновей. Интересно, почему же такое название у этой структуры?
Итак, придумаем решение за на запрос. Давайте отсортируем массив по значениям, и построим MergeSortTree по индексам этого массива. Для примера вот картинка:
картинка

Поймем, сколько элементов из [L; R] в поддереве, за которое отвечает данная вершина в дереве отрезков. На самом деле это очень просто посчитать: давайте возьмем lower_bound по L и R и найдем разность между ними — это и будет наше количество элементов. А теперь двоичными спусками будем находить k-тый элемент с помощью предыдущего утверждения. Заметим, что массив у нас отсортирован, поэтому мы получим именно k-тый элемент.

Решение за log^2 на запрос

А теперь то, зачем мы все здесь собрались, расскажу о fractional cascading. Давайте помимо отсортированных массивов в вершине хранить еще два: l и r, такие что l[i] означает количество элементов в левом поддереве, которые не больше a[i], аналогично c r. По сути эти массивы означают upper_bound. Аналогично можно завеcти и lower_bound.
Картинкой построение upper_bound:
гифочка как строится fraction cascading
Вернёмся к задаче и поймем, что теперь вместо бинпоиска в сыновьях мы можем просто перейти по этим индексам L и R и найдем опять наш отрезок [L1; R1], в котором лежат только индексы из [L0; R0]. Итого нам придется только двоично спускаться по дереву, поэтому сложность на запрос.

Решение за log n на запрос

В целом, fraction cascadinbg используется в задачах на MergeSortTree, в которых требуется каждый раз бинпоиском искать что-то в сыновьях.

3) Научимся решать задачи на запросы в оффлайн, которые вы можете сделать на обычном ДО, но с возможностью добавления и удаления элементов. Для этого нам надо понять относительный порядок элементов, если бы мы не удаляли элементы.
Давайте заведем неявное ДД; для каждого элемента будем хранить 0 или 1 — удален этот элемент или нет соответственно, а так же будем сохранять количество неудаленных в поддереве(еще чтобы в конце выполнить запросы, требуется хранить номера запросов, которые добавили и удалили данный элемент). Тогда напишем ещё одну операцию split1, которая будет аналогично split разрезать дерево на 2, но в split1 будет разрезать по количеству еще не удалённых элементов в правом дереве. Теперь с помощью split1 и стандартного merge мы можем добавлять и удалять элементы(вместо удаления нам просто нужно поставить 0 в элемент на позиции pos среди неудаленных).
Теперь мы получили относительный порядок элементов, можно построить дерево отрезков и выполнять наши операции, а вместо удаленных или еще недобавленных элементов можно записать фиктивные значения.
Сложность построения:

В целом, эта мини-лекция была подготовительной для дальнейших и является базовой и необходимой в олимпиадном программировании.
Если что-то не понятно, задавайте вопросы в комментариях, объясню более подробно

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Кажется, во втором пункте вы загнали лажу.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Я обновил описание l и r по-другому: l[i] означает количество элементов в левом поддереве, которые не больше a[i], аналогично c r. Тогда становится понятно, что с помощью такой информации можно восстановить новые индексы при переходе в левое и правое поддерево, означающие upper_bound от l и r. Нужно только разобраться с +-1

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я в начале невнимательно прочитал и ошибся, на самом деле решение работает :)

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

По поводу fractional cascading: нужно чётко понимать, что этот алгоритм скорее теоретический и в реальности работает медленно (хороший log ^ 2 быстрее).

Подробнее: https://codeforces.me/blog/entry/21892

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Нет, у fractions cascading абсолютно нет константы, поэтому там log. Например в иннополисе именно k-тую статистику не сдать без этой оптимизации.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну, насколько я помню, я смог запихать туда фенвика (правда уже после того, как FC написал). То что говорит Вова — имееет смысл, опять таки — у тебя в целом достаточно плохая реализация алгоритма за log * log.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Более того, мне на реальной олимпиаде попадалась задача, которая без fractional cascading в онлайн не заходит