Каков наилучший способ реализовать этот тип бинарного дерева?

Question

Допустим, у меня есть двоичное дерево высотой h, в котором есть элементы x1, x2, ... xn.

Элемент xi изначально находится на i-м левом листе.Дерево должно поддерживать следующие методы за время O (h)

1. add (i, j, k), где 1 <= i <= j = <n.Эта операция добавляет значение k к значениям всех крайних левых узлов, которые находятся между i и j.Например, операция добавления (2,5,3) увеличивает все самые левые узлы, которые находятся между 2-м и 5-м узлами, на 3. </p>

2. get (i): возвращает значение i-го левого листа.

Что должно храниться во внутренних узлах для этих свойств?

Примечание: я не ищу точного ответа, но есть подсказка о том, как подойти к проблеме.было бы здорово.

Answer 1

Насколько я понимаю, позиция xi'th элемента никогда не меняется, и дерево не является деревом поиска, поиск основан исключительно на позиции узла.

Вы можете сохранить смещение в вершинах без листьев, указывающих на изменение значения его потомка.

add(i,j,k) начнется с корня, углубится в дереве и увеличит значение узла наk тогда и только тогда, когда все его потомки находятся в диапазоне [i,j].Если это увеличило значение, дальнейшее углубление не произойдет.
Примечание 1: В одной операции add() может потребоваться добавить более одного числа.
Примечание 2: На самом деле вам нужно добавить не более O(logn) = O(logh) значений [убедитесь сами, почему.Подсказка: двоичное представление числа до n требует O(logn) бит], что позже дает вам [снова, убедитесь, что вы понимаете, почему] O(logh) необходима сложность.: суммируйте значения от корня до i-го листа и верните эту сумму.

Поскольку это кажется домашней работой, я не буду публиковать псевдокод, это руководство должно помочь вам начать работу с этим заданием.