Правильно ли я понял, что нам нужно среди всех подотрезков отрезка [X;Y] найти тот, сумма на котором максимальна?

Если да, то это относительно несложно.

Во-первых, подсчитаем префиксные суммы для всех отрезков [0;i], назовем их sum[i].

Пусть у нас есть отрезок [X;Y], и мы его как-то разобьем на две части: [X;M] и [M + 1;Y]. Тогда оптимальный ответ может выглядеть следующим образом:

1. Он является подотрезком первого отрезка.
2. Он является подотрезком второго отрезка.
3. Левый конец лежит в первом отрезке, а правый — во втором.

Первые два случая тривиальны, а оптимальный ответ третьего типа выглядит так: берется максимум среди sum[i] на отрезке [M + 1;Y] — это будет правым краем отрезка, и берется минимум среди sum[i - 1] на отрезке [X;M] — это левый край.

Итого нам нужно в каждой вершине дерева отрезков хранить три вещи: максимум среди sum[i] на этом отрезке, минимум среди sum[i - 1] на этом отрезке и оптимальный ответ на этом отрезке.

Если что-то не понятно — скажите, что именно.

Кодфорсчане) На лурке сидишь?)