CODEWITHSUNDEEP
arraysalgorithmdata-structuressegment-tree
keemahs
keemahs

Reputation: 998

Compute sum of (min*max) across all subarrays of the array

given N elements of an array compute the sum (min*max) across all the subarrays of the array.

e.g. N = 5

Array: 5 7 2 3 9

output: 346 (5*5 + 7*7 + 2*2 + 3*3 + 9*9 + 5*7 + 2*7 + 2*3 + 3*9 + 2*7+2*7 + 2*9 + 2*7 + 2*9 + 2*9)

here is the complete question

i cannot think of anything better than O(n^2). The editorial solution uses segment trees which i couldnt understand.

Upvotes: 1

Views: 515

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Hint regarding the editorial (the details of which I am uncertain about): if we can solve the problem for all the intervals that include both A[i] and A[i+1], where i divides A in half, in O(n) time, then we can solve the whole problem in O(n log n) time using divide and conquer, solving left and right separately, and adding to that the intervals that overlap both left and right.

input:
5 7 2|3 9
    i      (divides input in half)

Task: find solution in O(n) for all intervals that include 2 and 3.

5 7 2 3 9
    xxx
      2 2  -> prefix min
2 2 2      <- prefix min
      2 4  -> prefix sum min
6 4 2      <- prefix sum min
      3 9  -> prefix max
7 7 3      <- prefix max

Notice that because they are monotonically increasing, maxes can be counted as extending back to the next higher element into the opposite prefix. For example, we can find that the 7 extends back to 9 by extending pointers in either direction as we mark the current max. We then want to multiply each max by the relevent min prefix sum.

Relevant contributions as we extend pointers marking current max, and multiply max by the prefix sum min (remembering that intervals must span both 2 and 3):

3 * 2
7 * 2
7 * 2
9 * 6

These account for the following intervals:

5 7 2 3 9
    ---
  -----
-------
    -----
  -------
---------

3*2 + 7*2 + 7*2 + 9*2 + 9*2 + 9*2

Now solve the problem for left and right separately and add. Doing this recursively is divide and conquer.

Upvotes: 1

Related Questions