Здравствуйте, NoHate, Вы писали:

NH>Может быть я недостаточно разобрался с вашим решением, но я попробовал хранить текущий коэффициент и текущий остаток и встретился вот с такой проблемой:
NH>http://rsdn.ru/forum/alg/6252178.1

Автор: watchmaker
Дата: 20.11.15

Корректировка всех узлов на ярусе весьма накладная вещь, не так ли?

Блин, я там соврал. Корректировать надо не ярус, а только правых соседей в страницах от текущей вверх до корня. А это — логарифмическое время.
Для страничных деревьев (Б- и иерархические) это выглядит вот так

0 ------------------------------------------------------------------> t

0---------------------------------------------------------------Z  в корневой странице можно держать итог от и до
 \
  o-----------------------------Y---Y---Y
 /   |                            |   |  \
     o---o-----------Y---Y----Y           o----o----o----o
    /  |    |          |    |  \         /  |    |    |   \
            o-X-Y-Y                   oooo oooo oooo oooo oooo
           / | | | \

o - нетронутые
X - текущий
Y,Z - изменяемые вслед
страницы зрительно растянуты, чтобы упорядочить все ключи по времени

То есть, если у нас иерархия дни-месяцы-года, то нужно
— поменять остатки (и градиенты) в днях, начиная с текущего
— в месяцах, начиная со следующего (но не в днях внутри месяцев)
— в годах, начиная со следующего (но не в месяцах и днях там)

Для двоичных

0 --------------------> t

            Y
   ________/ \
  o           o
 / \____
o       Y
       / \
      X   o
     / \
    o   o

Если X — левый ребёнок, то родителя нужно корректировать (он "следующий" по времени), если правый — не нужно.
Корректировать вниз не нужно вообще, потому что, по правилам расчётов, итоговое значение — это сумма значений на узлах от корня до текущего. И правки будут учтены автоматически.


Для Б+ деревьев всё хуже, т.к. данные только в листьях, а в остальных страницах лишь ключи (метки времени).
Мы же с самого начала делаем augmented tree.