Some time ago, I was solving the problem and got the following subtask. Actually, then found out that this was not necessary, but I wonder how to solve it.
The problem: Given an array A of N integers and Q queries, for each query you should find the minimum sum starting from the given position i. Let's say there are no updates and -1e9 <= A[i] <= 1e9, N <= 1e6, Q <= 1e6. Preprocessing at most O(N) and each query at most O(Log N).