Видимо, для задачи поиска подотрезка с максимальной суммой можно обрабатывать онлайн-запросы поиска на подотрезке [l;r] за O(log(N)).
Будем считать, что в конце данного отрезка записана -inf. Рассмотрим следующую декомпозицию: разобьем изначальный отрезок на участки [a;b] такие, что любой собственный префикс [a;x] будет иметь неотрицательную сумму, а сам [a;b] - отрицательную. Такое разбиение можно получить простейшим линейным алгоритмом. Заметим, что если для некоторого суффикса [x;n-1] построить подобное разбиение, то подотрезок этого разбиения не может находиться в общем положении с подотрезком суффикса [y;n-1] (иначе общая часть будет префиксом, т.е. иметь неотрицательную сумму, и суффиксом, т.е. иметь отрицательную).
Заметим также, что запрос максимальной суммы при фиксированной левой границе отрезка можно сделать через RMQ для частичных сумм.
Заметим, что для любой последовательности максимальная сумма получается на некотором префиксе некоторого отрезка разбиения.
Предпросчитаем для каждого индекса последовательности значение end[j] - окончание первого отрезка разбиения суффикса [j;n-1]. С учетом сказанного выше это можно сделать за O(N) при помощи стека, умеющего делать общее добавление (аккумулятор + вычитание из приходящего). Предпросчитаем для каждого i ответ на отрезке [j;end[j]], заметив, что он достигается, когда левая граница ответа находится в j (это отрезок разбиения [j;end[j]]).
Теперь к нам приходит запрос [l;r]. Мы полностью покрываем все подотрезки вида [j;end[j]] для диапазона l <= j < x, где x - минимальный на [l;r] такой, что end[x] > r. Но [x;end[x]] является отрезком разбиения [l; n-1], значит, [x,r] является отрезком разбиения [l;r], значит, ответ в нем лежит на некотором его префиксе.