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

Дерево отрезков
Автор CleverDoner, 10 лет назад, По-русски

Всем привет.

Можете ли вы подсказать как написать дерево отрезков с запросами видов:

  • l r x умножить все числа в отрезке с l по r на х

  • l r x прибавить ко всем числам в отрезке с l по r х

  • ? р вывести элемент на позиции р

Заранее спасибо.

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

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

Дерево отрозков: обновление на отрезке

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

    Спасибо, кэп. К счастью я знаю о существование этого сайта. Хотелось бы узнать как одновременно умножать и плюсовать с помощью проталкивание!!!

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

      Ну тогда почитай, там хорошие объяснения

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

Можно и без проталкивания. В каждой вершине будем хранить toAdd, toMult. Когда проходим вершину будем ответ умножать на toMult/добавлять toAdd. Будем ходить снизу вверх.

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

Два push(), для умножения и для прибавления! А можно ссылку на задачу?

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

    А как узнать что делать раньше, умножение или прибавление?

    Республиканская-2013(Казахстан) задача F.

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

Модификация должна хранится в виде двух чисел: mul — на что умножить число, и add — что к нему прибавить. Если нужно в "модификацию" добавить умножение на x, то mul *= x, add *= x, если добавить x то add += x; И дерево отрезков с проталкиванием.

→ Ответить