MaxRokatansky Jan 23 2020 at 14:48Дерево отрезков: просто и быстроReading time5 minViews34KOTUS corporate blogAlgorithms*Total votes 23: ↑23 and ↓0+23Add to bookmarks99Comments6
Andy_U Jan 23 2020 at 15:03А почему не посчитать кумулятивную сумму и дальше находить ответ за одно вычитание?
FFormula Jan 23 2020 at 16:53Show previous commentПотому что в общем случае этот алгоритм работает для любой ассоциативной функции, например, для нахождения минимума такой подход не годится.
Andy_U Jan 23 2020 at 18:11Comment has been editedShow previous commentА вот этого расширения я не заметил.
Akon32 Jan 23 2020 at 17:18Show previous commentРеализована ещё и операция быстрого обновления элементов массива — это требуется по условиям олимпиадной задачи.
Andy_U Jan 23 2020 at 18:06Comment has been editedShow previous commentВ первой половине статьи, где описывается постановка задачи, это требование, увы, анонсировано не было.
Akon32 Jan 23 2020 at 21:05Show previous commentЯ сам не сразу заметил, но обновление упомянуто во 2м предложении. Тоже удивился, почему кумулятивную сумму не считают.
Дерево отрезков: просто и быстро