### overwrite's blog

By overwrite, history, 7 weeks ago,

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).

• +1

 » 7 weeks ago, # |   0 Sounds like you could get somewhere with a modification of Kadane's?
 » 7 weeks ago, # |   +10 what about a segment tree that maintains the minimum sum over the interval, and answers queries using sum(i,n) ?
•  » » 7 weeks ago, # ^ |   +6 That should work, but bit overkill. I liked SuperJ6's approach.
 » 7 weeks ago, # |   +11 Compute prefix sum, iterate backwards, hold lowest prefix sum, subtract from query position prefix sum.
•  » » 7 weeks ago, # ^ |   +3 Cool!
 » 6 weeks ago, # |   0 The Harder of version of this can be found here.