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

NH>Здравствуйте, Кодт, Вы писали:

К>>В моей модели проблемы нет.
К>>Как я уже предлагал, каждый узел хранит пару (s,s') — текущий остаток и текущий градиент.

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

Как мне кажется, между решениями, предложенными мною и Кодтом, принципиальных отличий нет.
Из непринципиальных же можно выделить такую пару:
В-первых, у Кодта хранится в узле дерева градиент, сумма и время (как ключ), а у меня изначально лишь градиент и время. То есть по-сути отличие в том, будем-ли мы раскрывать скобки в выражении k(x-t) или сохраним как есть. Подход без раскрытия требует меньше памяти, но, очевидно, плохо совместим с мгновенными изменениями (зря про них сразу не сказал :) ). Так что в итоге всё равно в обоих решениях получилось по три числа на узел (время, градиент и сумма).
И во-вторых, я предлагал сохранять в дереве оригинальные данные, а суммирование достигать через аугментацию. В решении же Кодта ситуация обратная — в узлах дерева сразу же хранятся суммы, но теперь аугментация понадобится, если нужно будет доступ к оригинальным значениям, например чтобы отвечать на запрос об произведённых изменениях за конкретную дату. То есть тут разница лишь что считать первичным значением, а что вторичным.

В остальном все операции имеют свой прямой аналог и в другом решении. Оно и понятно — ведь используется практически стандартный подход для суммирования через деревья. Так что если увидишь у Кодта хорошую идею — смело используй, она точно так же сработает в обоих алгоритмах :)