Блог пользователя 012-26021-Maksat-8

Слыхали про дерево отрезков?
Автор 012-26021-Maksat-8, история, 6 лет назад, По-русски

Очень хотелось бы узнать и понять алгоритм дерева отрезков. Я смотрел много источников но не смог ни код написать, ни на практике использовать. А именно больше всего хотелось бы узнать реализацию и теорию прибавления на отрезке. Хочу заранее поблагодарить того кто поможет!!!

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

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

Не рановато ли тебе его учить?)

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

    Учить что-то никогда не рано. Если человеку интересно, то пусть изучает.

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

Ну можешь глянуть курс по алгоритмам Дениса Павловича Кириенко на Фоксфорде (я в свое время по нему изучал ДО).

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

    Забыл сказать. Чтобы понять Дерево отрезков нужно хорошо понимать бинарные деревья поиска. Так что если ты не изучал их, то рекомендую ознакомиться. По сути ДО — это не какая-то "особенная" структура данных, а простое бинарное дерево, в каждой ячейке которого хранится информация о каком-то отрезке (полуинтервале).

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

    Можно разве что понять, как это работает, но писать, как написано в курсе не советую т.к. в свое время тоже по нему учил и теперь пишу по привычке на этих указателях(. Стоит писать не на указателях, а на массивах, одна из самых главных причин — дебаг. Вроде как скорость на указах тоже поменьше

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

      Да, на указателях гораздо медленнее. Ну реализацию можно на emaxx взять.

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

https://e-maxx.ru/algo/segment_tree, тут подробно описаны дерево отрезков и его разные вариации.

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

http://brestprog.by/topics/segmenttree/ — тут и визуализация в картинках есть, и объяснено неплохо.

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

https://www.youtube.com/channel/UC_Y39KfAPRCUb4d7ksys5NQ

→ Ответить