Дан массив, состоящий из целых чисел. По данным запросам найти максимально возможную сумму в диапазоне

Question

Вам дана последовательность A [1], A [2], ..., A [N]. (| A [i] | ≤ 15007, 1 ≤ N ≤ 50000). Запрос определяется следующим образом: Query (x, y) = Max {a [i] + a [i + 1] + ... + a [j]; x ≤ i ≤ j ≤ y}. Учитывая M запросов, ваша программа должна вывести результаты этих запросов.

Я реализовал деревья сегментов для этой проблемы. В возврате запроса и построении дерева сегментов я реализовал эту стратегию, и она выдает ошибку «Превышен лимит времени». Пожалуйста, помогите!

return max(
    getSumUtil(st, ss, mid, qs, qe, 2*si+1) + getSumUtil(st, mid+1, se, qs, qe, 2*si+2),
    getSumUtil(st, ss, mid, qs, qe, 2*si+1), 
    getSumUtil(st, mid+1, se, qs, qe, 2*si+2)
    ); 

Где getSumUtil - это служебная функция, которая в основном является функцией запроса для проблемы