计算数组所有子数组的 (min*max) 之和

Question

给定数组的 N 个元素，计算数组所有子数组的总和 (min*max)。

例如 N = 5

数组：5 7 2 3 9

输出：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)

我想不出比 O(n^2) 更好的了。编辑解决方案使用了我无法理解的线段树。

Answer 1

关于社论的提示（我不确定的细节）：如果我们可以解决包含 A[i] 和 A[i+1] 的所有区间的问题，其中 i 将 A 一分为二，在 O(n) 时间内，然后我们可以在 O(n log n) 时间内使用分而治之的方法解决整个问题，分别解决左和右问题，并在其中添加间隔左右重叠。

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

任务：在 O(n) 中找到包含 2 和 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

请注意，因为它们是单调递增的，所以最大值可以算作延伸回下一个更高的元素进入相反的前缀。例如，当我们标记当前最大值时，我们可以通过向任一方向扩展指针来发现 7 扩展回 9。然后我们想将每个最大值乘以相关的最小前缀和。

当我们扩展标记当前最大值的指针并将最大值乘以前缀和最小值时的相关贡献（记住间隔必须跨越 2 和 3）：

这些占以下时间间隔：

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

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

现在分别解决左右问题并添加。递归地执行此操作是分而治之。

计算数组所有子数组的 (min*max) 之和

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

arrays

algorithm

data-structures

segment-tree