Очистить диапазон (установить диапазон на ноль) модификация ленивого сегмента

Я хотел бы добавить функцию к реализации отложенного распространения в ссылке ниже, которая устанавливает диапазон на 0. В настоящее время там есть функция update_tree, которая увеличивает диапазон, но я не знаю, как изменить его так, чтобы он установил бы диапазон равным нулю лениво за время O (log (N)).

http://se7so.blogspot.com.au/2012/12/segment-trees-and-lazy-propagation.html

Я думаю об использовании флага «lazy clear» на каждом из узлов, но как я узнаю, что сначала нужно очистить, затем добавить lazy или добавить add, а затем очистить (что было бы просто ясно)?

0

Решение

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]