我正在学习二叉树!我在这个家庭作业中有一个问题。我必须用二叉树来解决这个问题问题是:给你一个整数列表。然后，您需要回答一些类似这样的问题:"列表内容的元素在索引a和索引B之间的最大值是多少?"例子:
INPUT :
10
2 4 3 5 7 19 3 8 6 7
4
1 5
3 6
8 10
3 9
OUTPUT:
7
19
8
19
时间限制和内存(语言:c++)
时间:在1GHz机器上0.5s。内存:16000 KB
约束1 <= N <= 100000，其中N为列表中的元素个数。
1 <= A, B <= N，其中A, B为区间的极限。
1 <= I <= 10000，其中I为区间数。
请不要给我解决方案，只是一个提示!非常感谢!
正如在评论中已经讨论过的那样，为了使事情简单，您可以向数组中添加条目，使其大小为2的幂，因此二叉树对所有叶子具有相同的深度。向列表中添加什么元素并不重要，因为在实际算法中不会使用这些计算值。
在二叉树中，你必须以自下而上的方式计算最大值。这些值告诉你这些节点所代表的整个范围的最大值;这是树的主要思想。
剩下的是将查询拆分为这样的树节点，因此它们使用比间隔大小更少的节点来表示原始间隔。找出树节点所代表的间隔的"模式"。然后找出一种方法将输入间隔分割成尽可能少的节点。也许可以从简单的解决方案开始:将输入拆分为左节点，即单个元素。然后找出如何使用树的内部节点来"组合"间隔中的多个元素。通过而不是使用树(因为这将需要元素数量的线性时间，但树的整体思想是使其成为对数)来为您找到一个算法。
编写一些代码，在间隔大小为0的情况下工作。这很简单。
然后为大小为1的区间写一些。它仍然是简单的。
然后为大小为2的区间写一些。这可能需要一个比较。它仍然是简单的。
然后为大小为3的区间写一些。它可能涉及到选择哪个大小为2的区间进行比较。这并不太难。
一旦你这样做了，应该很容易使它工作在任何间隔大小
数组将是解决这个问题的最佳数据结构。
但是如果您需要使用二叉树，我会将(索引，值)存储在二进制文件中