Как прибавлять лесенки на отрезке?

Я слышал, что используя дерево отрезков можно прибавлять лесенки на отрезке, то есть убывающие или возрастающие массивы, где разница между соседними элементами равна 1. Как это сделать?

1 симпатия

Не связано с вопросом, но мне жутко интересно: @AnsarYesma сколько символов в минуту печатаешь?

1 симпатия


Ваш сайт отслеживает скорость печатания???

1 симпатия

Сообщение про оригами было указано как возможный спам, из-за быстрого набора

литералли 1984

1 симпатия

Прибавить лесенку на отрезке - прибавлять арифметическую прогрессию с шагом k. Если ты про это то тогда это можно сделать с помощью проталкивания. Допустим ты хочешь уметь считать сумму на отрезке и прибавлять лестницу на отрезке. Это легко делается так:
В вершине храним три значения, текущую сумму на отрезке, значение которое нужно прибавить к каждому элементу на отрезке и количество лесенок вида {0, k, 2k, 3k, ...} которые нужно прибавить к отрезку, сначала научимся прибавлять обычную арифметическую прогрессию вида {1, 2, 3, …}. Давай заметим что мы можем аккуратно проталкивать значения и поддерживать сумму в вершине. Будем рассматривать проталкивание :

  1. Что изменится в текущей вершине v, ну очевидно что sum[v] станет равным sum[v] + (r - l + 1) * add[v] + ((r - l + 1) * (r - l + 2) / 2) * lads[v] где l и r границы отрезка вершины v, а lads[v] и add[v] станут равными 0.
  2. Как протолкнуть апдейт в детей? Очевидно что add[v] мы можем проталкивать как в обычном прибавлении на отрезке. Чтобы проталкивать lads[v] заметим что можно разделить лестницу на две лестницы и один прямоугольник под второй лестницей:
    image
    Воспользуемся этим и протолкнём отдельно первую лестницу на отрезок l...m, вторую лестницу на отрезок m + 1...r, и прямоугольник отдельно на отрезок m + 1...r. Протолкнуть прямоугольник очень легко, так как это тоже самое что добавить ко всем элементам на отрезке m + 1...r значение m - l + 1. Теперь чтобы протолкнуть lads[v] мы должны сделать так lads[v * 2] = lads[v * 2] + lads[v], lads[v * 2 + 1] = lads[v * 2 + 1] + lads[v], и add[v * 2 + 1] = add[v * 2 + 1] + (m - l + 1) * lads[v].

Теперь мы умеем проталкивать обновление. Функцию обновления отрезка можешь придумать сам, это не сложно. Придумать как прибавлять другие арифметические прогрессии тоже не сложно.

Вот задача для практики : CSES - Polynomial Queries

Вот моя реализация

Обычные обновления с ленивым проталкиванием : MAXimal :: algo :: Дерево отрезков

5 симпатий

Видимо анти-спам система да.

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

image

гы.

К слову, любой сбор данных от имени Фонда отображен тут

1 симпатия