overwrite's blog

By overwrite, history, 7 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Sounds like you could get somewhere with a modification of Kadane's?

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

what about a segment tree that maintains the minimum sum over the interval, and answers queries using sum(i,n) ?

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Compute prefix sum, iterate backwards, hold lowest prefix sum, subtract from query position prefix sum.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The Harder of version of this can be found here.