Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Сжатое дерево отрезков
Автор Vaness, 12 лет назад, По-русски

Можно ли где-то почитать про сжатое дерево отрезков? А то простое гугление на первый взгляд не выдает ничего хорошего.

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

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

А можно подробнее про то, что вы имеете в виду?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Структура данных, которая может выполнять те же операции, что и обычное дерево отрезков, только сами отрезки, на которых мы узнаем значение функции, имеют координаты не [1, n], где n — достаточно маленькое число, а, допустим, [1, 10^9].

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Да ну. Как это не обойтись без дерева поиска.

        Что мешает сделать динамическое дерево, у которого у каждой вершины ребёнок может равняться NULL, что будет значить значение по умолчанию для всех элементов дерева (например, для дерева с суммой — значение ноль для всех элементов поддерева). Тогда если раньше функция запроса имела вид get_sum(int l, int r, int L, int R, int v), то сейчас она будет иметь значение get_sum(int l, int r, node* v), причём для v == NULL она будет возвращать ноль.

        Соответственно, когда надо будет обратиться к отрезку, вершины для которого, пока не существует, мы, спускаясь до него рекурсивно, просоздаём все несуществующие вершины дерева.

        В общем, это ответ на вопрос автора.

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

          Да-да, я уже понял и дописал)

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

          Ок, теперь понятно.

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

          Я когда не знал такого ресурса как e-maxx и как нормально закодить дерево отрезков, кодил именно динамическое дерево :)

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

может метод сжатых координат?

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Если я правильно понял, то мне это объясняли как "неявное дерево", принцип следующий: мы не будем создавать вершину, пока она нам не понадобиться. На каждом запросе мы создадим не более logN вершин. Вот так.

Хотя может быть автор имеет ввиду дерево отрезком по сжатым координатам?

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

Меняю ссылку на подходящую задачу на тимусе на аккуратно написанный (в будущем) мной код :). Мне понравилась идея, никогда не писал этого раньше.

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

Если кому интересно, то вот код задачи F с Жаутыковской олимпиады 2012 с этим деревом: http://pastebin.com/rjXM0bJv

→ Ответить