How to handle the queries in which there is partial overlap?

#1

I am not able to understand that how can we handle those queries in which there is partial overlap.

Question Link: https://www.spoj.com/problems/GSS1/

#2

As you know, you need to use a segment tree. The only question is what data to store in each node. As you know, the requirement should be that it is easy to compute the data associated with a given interval if you already know the data associated with two subintervals whose disjoint union is the given interval. I claim that the data you need are:

  • the max nonempty subarray sum,
  • the max nonempty prefix sum,
  • the max nonempty suffix sum,
  • the total sum.

To compute the max nonempty subarray sum for an interval I which is the disjoint union of a left subinterval L and a right subinterval R, consider three cases:

  1. The max sum nonempty subarray is contained within L. In that case, it is the max sum nonempty subarray of L, which we already know.
  2. The max sum nonempty subarray is contained within R. In that case, it is the max sum nonempty subarray of R, which we already know.
  3. The max sum nonempty subarray is partly in L and partly in R. In that case, it must be the combination of the maximum sum nonempty suffix of L and the maximum sum nonempty prefix of R, which we know.

To get the max nonempty subarray sum for a given interval, just take the max of these three cases. I don’t think there’s much to prove here: it’s nothing other than case analysis. I leave it to the reader how to figure out how to calculate the max nonempty prefix sum and max nonempty suffix sum for an interval from the subintervals. The total sum is, of course, standard.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.