Comments 6
В принципе, все это уже описано, например, здесь:
www.e-olimp.com/articles/15 (даже иллюстрация такая же, пусть и не цветная).
В любом случае, спасибо за код — кому-нибудь может пригодиться. Еще отличная заметка о дереве Фенвика есть на TopCoder'e.
www.e-olimp.com/articles/15 (даже иллюстрация такая же, пусть и не цветная).
В любом случае, спасибо за код — кому-нибудь может пригодиться. Еще отличная заметка о дереве Фенвика есть на TopCoder'e.
По обеим ссылкам тривиальная реализация с возможностью изменения одного элемента, а не отрезка
Мне больше всего описание дерева Фенвика нравится здесь e-maxx.ru/algo/fenwick_tree
поясните, что именно хранится в массивах m и mt, при каких условиях туда что прибавляется, с какими коэффициентами суммируется.
В массиве m хранится сумма на отрезке (без учёта полностью накрываемых запросов модификации), а в массиве mt, соответственно, — число, которое надо прибавить к каждому элементу отрезка.
Тогда, при модификации, для зелёных отрезков заносим в mt, а для синих — в m (так как они шире запроса). А при суммировании зелёные отрезки считаем как обычно + учитываем значения в mt, а для синих — только mt. Коэффициенты получаются из длины соответствующего отрезка, с помощью тех же формул, что и для перемещения между столбцами, в приведённых фрагментах кода их видно.
Тогда, при модификации, для зелёных отрезков заносим в mt, а для синих — в m (так как они шире запроса). А при суммировании зелёные отрезки считаем как обычно + учитываем значения в mt, а для синих — только mt. Коэффициенты получаются из длины соответствующего отрезка, с помощью тех же формул, что и для перемещения между столбцами, в приведённых фрагментах кода их видно.
Sign up to leave a comment.
Дерево Фенвика с модификацией на отрезке