MaxRokatansky 23 янв 2020 в 14:48Дерево отрезков: просто и быстроВремя на прочтение5 минКоличество просмотров36KБлог компании OTUSАлгоритмы*Всего голосов 23: ↑23 и ↓0+23Добавить в закладки100Комментарии6
Andy_U 23 янв 2020 в 15:03А почему не посчитать кумулятивную сумму и дальше находить ответ за одно вычитание?
FFormula 23 янв 2020 в 16:53Показать предыдущий комментарийПотому что в общем случае этот алгоритм работает для любой ассоциативной функции, например, для нахождения минимума такой подход не годится.
Andy_U 23 янв 2020 в 18:11Комментарий был измененПоказать предыдущий комментарийА вот этого расширения я не заметил.
Akon32 23 янв 2020 в 17:18Показать предыдущий комментарийРеализована ещё и операция быстрого обновления элементов массива — это требуется по условиям олимпиадной задачи.
Andy_U 23 янв 2020 в 18:06Комментарий был измененПоказать предыдущий комментарийВ первой половине статьи, где описывается постановка задачи, это требование, увы, анонсировано не было.
Akon32 23 янв 2020 в 21:05Показать предыдущий комментарийЯ сам не сразу заметил, но обновление упомянуто во 2м предложении. Тоже удивился, почему кумулятивную сумму не считают.
Дерево отрезков: просто и быстро