Дерево отрезков: просто и быстро

[Andy_U]

А почему не посчитать кумулятивную сумму и дальше находить ответ за одно вычитание?

[FFormula]

Потому что в общем случае этот алгоритм работает для любой ассоциативной функции, например, для нахождения минимума такой подход не годится.

[Andy_U]

А вот этого расширения я не заметил.

[Akon32]

Реализована ещё и операция быстрого обновления элементов массива — это требуется по условиям олимпиадной задачи.

[Andy_U]

В первой половине статьи, где описывается постановка задачи, это требование, увы, анонсировано не было.

[Akon32]

Я сам не сразу заметил, но обновление упомянуто во 2м предложении. Тоже удивился, почему кумулятивную сумму не считают.