我有以下问题: 假设你有一个数组 A 有 n 个不同的数字，并假设你可以将 n 个元素存储在新的数据结构中(一个可以帮助你解决下面问题的数据结构)，同时保存存储时间受 O(n) 限制. 为函数 max (i,j) 编写一个算法，它将获得两个大于 j 的索引 i 作为输入，并将返回 A[i]、A[i+1]、...、A[ 之间的最大值作为输出j]. max(i,j) 应该以 O(log(n)) 为界。
我考虑过二叉树，但想不出为什么要存储数字。我可以考虑的一个选项是创建一个“锦标赛树”，它需要 O(n) 的存储时间，但我没能找到使用这种数据结构的最大算法。
这是一道作业题，但找不到它的标签。
最佳答案
这是segment tree最典型的应用.
给定一个数字数组，你可以用O(n)在它上面构建一个段时间复杂度并对 O(logn) 中的间隔/范围执行查询时间。
一些常见的应用示例 - 从索引 i 中查找元素的总和至 j其中 0 <= i <= j <= n - 1 , 从索引 i 中查找元素的最大值/最小值至 j其中 0 <= i <= j <= n - 1等
关于algorithm - 在 O(log(n)) 的时间内找到数组中的最大值 - 有一些假设，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52155472/