Pull to refresh

Comments 6

В принципе, все это уже описано, например, здесь:
www.e-olimp.com/articles/15 (даже иллюстрация такая же, пусть и не цветная).

В любом случае, спасибо за код — кому-нибудь может пригодиться. Еще отличная заметка о дереве Фенвика есть на TopCoder'e.
По обеим ссылкам тривиальная реализация с возможностью изменения одного элемента, а не отрезка
поясните, что именно хранится в массивах m и mt, при каких условиях туда что прибавляется, с какими коэффициентами суммируется.
В массиве m хранится сумма на отрезке (без учёта полностью накрываемых запросов модификации), а в массиве mt, соответственно, — число, которое надо прибавить к каждому элементу отрезка.
Тогда, при модификации, для зелёных отрезков заносим в mt, а для синих — в m (так как они шире запроса). А при суммировании зелёные отрезки считаем как обычно + учитываем значения в mt, а для синих — только mt. Коэффициенты получаются из длины соответствующего отрезка, с помощью тех же формул, что и для перемещения между столбцами, в приведённых фрагментах кода их видно.
Спасибо, стало понятно. Просто стоит более понятно называть переменные, как минимум, m переименовать в sum, а mt — в add например :)
Only those users with full accounts are able to leave comments. Log in, please.