algorithm - 实现这种二叉树的最佳方法是什么？

Question

假设我有一棵高度为 h 的二叉树，其元素为 x1、x2、... xn。

xi 元素最初位于第 i 个最左边的叶子。树应该在 O(h) 时间内支持以下方法

1. add(i, j, k) 其中 1 <= i <= j =< n。此操作将值 k 添加到 i 和 j 之间的所有最左边节点的值。例如，add(2,5,3) 操作将第 2 和第 5 个节点之间的所有最左边的节点递增 3。

2. get(i):返回第 i 个最左边的叶子的值。

该属性的内部节点应该存储什么？

注意:我不是在寻找确切的答案，但任何关于如何解决问题的提示都会很好。

Answer 1

据我了解，第 xi 个元素的位置永远不会改变，并且该树不是搜索树，搜索仅基于节点的位置。

可以在非叶子顶点存储一个偏移量，表示其后代的值变化。

add(i,j,k) 将从根开始，深入树中，将节点的值增加 k 当且仅当其所有后代都在范围内 [i,j]。如果它增加了值(value)，则不会发生进一步的深化。
注意 1:在单个 add() 操作中，您可能需要添加多个数字。
注意 2:您实际上最多需要添加 O(logn) = O(logh) 值 [说服自己为什么。提示:n 以内的数字的二进制表示需要 O(logn) 位]，稍后会[再次确保您理解原因] O( logh) 需要复杂性。

get(i) 然后是微不足道的:总结从根到第 i 个叶子的值，并返回这个总和。

因为这似乎是作业，所以我不会发布伪代码，这个指南应该可以让你开始这个作业。