lucifer

背景

给一个两个数组,其中一个数组是 A [1,2,3,4],另外一个数组是 B [5,6,7,8]。让你求两个数组合并后的大数组的:

  • 最大值
  • 最小值
  • 总和

这题是不是很简单?我们直接可以很轻松地在 $O(m+n)$ 的时间解决,其中 m 和 n 分别为数组 A 和 B 的大小。

那如果我可以修改 A 和 B 的某些值,并且我要求很多次最大值,最小值和总和呢?

朴素的思路是原地修改数组,然后 $O(m+n)$ 的时间重新计算。显然这并没有利用之前计算好的结果,效率是不高的。 那有没有效率更高的做法?

有!线段树就可以解决。


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 。
载入天数...载入时分秒...