Dynamic max subvector sum

[bbi5291]

OK, here's a nice problem for those of you very algorithmically inclined:
You are given a vector of 100000 numbers and 100000 commands to be executed in order. There are two types of commands.
* Modify command: Specifies an index into the vector and a value to which to change the current value of the element at the specified index. For example, it might be encoded as "M 3 -5", meaning to change the element at index 3 to -5.
* Query command: Specifies two indices into the vector, in effect specifying a subvector of the original vector. For example, if the original vector were (1 -2 3 -4 5 -6) and zero-based, the indices 2 and 4 would specify the subvector starting at index 2 and ending at index 4, or (3 -4 5). Now given this subvector, you want to find its subvector such that the sum of the elements within is maximal, and report that maximal sum. For example, in the query given, the subvector of (3 -4 5) with the maximal sum is (5). Hence the answer to the query "Q 2 4" would be the sum of this subvector, which is merely 5.

How do you solve this problem efficiently?

Bits will be awarded for the solution to this difficult problem. Please be honest and don't use online resources.

[chopperdudes]

i'm taking this requires more efficiency than merely dp'ing to find the subvector sum?

might try if you include an input file.

[bbi5291]

Ahh, but then I'd have to specify an input format, which is annoying.
The problem with the DP approach is that it takes linear time per query. With 100000 elements and 100000 queries, that will time out.

[Brightguy]

How about this (brief) sketch:

Let x be the input vector of size n. Compute the running total y, i.e., y(i) = sum(x(1..i)). Solving the query "Q p q" is equivalent to finding the largest "jump" in y(p..q), i.e., finding the best "jump indices" i and j>i such that y(j)−y(i) is maximized and p<=i,j<=q (this can be done in linear time in q−p).

Note that if we know the best jump indices for the range [p, q] and [q, r] and their jump values then we can easily "merge" and find the best jump indices and jump value for the range [p, r].

Preprocessing: We start off by noting the trivial jump indices for the ranges [1, 1], [2, 2], ..., [n, n]. Then by merging these we find the jump indices for the ranges [1, 2], [3, 4], ..., [n−1,n]. And by merging these we find the jump indices for [1, 4], [5, 8], ..., [n−3, n], etc. until we know the jump indices and jump value for [1, n].

We can now solve the query command "Q p q" efficiently by looking at the previously computed jump indices from the ranges which lie entirely between p and q and merging ranges appropriately. To limit the number of merges required we only consider the jump indices from the longest intervals possible and ignore the ones from subintervals of these, since they can never yield a better jump.

To deal with the modify command at index m, note that this adds a constant to y(i) for i≥m. The jump indices (and jump values) from the precomputed ranges which cross m may have to be recomputed (there are O(log(n)) of them).

[bbi5291]

Describe how to carry out this merge step in constant time?

[Brightguy]

I guess if i and j are the jump indices on a range and h and k are the indices of the min/max values on a range (and i', j', h', k' are those indices for the range you are merging with) then the new jump indices after a merge would be either (i, j) or (i', j') or (h, k'), whichever leads to the biggest jump.

So I should've said you also have to keep track of the min/max indices in addition to the jump indices.

[bbi5291]

Well, it's not fully complete, but you have the right idea Yes, you use a segment tree, and I think this is the optimal solution, taking logarithmic time per query.