Дерево Фенвика с модификацией на отрезке

Запрос отдельных элементов и модификация на отрезке

Если в задаче требуется производить изменения на отрезке и возвращать значения отдельных элементов, то пусть массив a[] хранит не сами элементы, а разности текущего и предыдущего элементов. Тогда, чтобы увеличить все элементы на отрезке l..r на величину val, достаточно добавить val к a[l] и добавить -val к a[r + 1] (две операции add), а чтобы вывести фактическое значение элемента в позиции pos, достаточно вернуть сумму a[1] + a[2] + ... + a[pos] (операция sum).

Запрос на отрезке и модификация на отрезке

Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то поступим следующим образом. Во-первых, пусть имеют место все соображения, изложенные в предыдущем абзаце. Далее, пусть сумма на отрезке 1..r выражается как a[r] * r - a1[r]. Осталось понять, как будут изменяться элементы a1[] при обновлениях на отрезках a[]. Пусть ко всем элементам a[] на отрезке l..r добавлено значение val. Рассмотрим значение суммы элементов a[] на отрезке 1..pos:

• Если pos < l, то реальная сумма не изменилась, а сумма, рассчитываемая по указанной выше формуле, также не изменилась и соответствует реальной;
• Если l <= pos <= r, то к реальной сумме добавится (val * (p - l + 1)), а к сумме, рассчитываемой по указанной ранее формуле, — (val * pos). Чтобы расчётное значение соответствовало реальному, ко всем элементам a1[] с индексами не меньше l нужно добавить (val * (l - 1));
• Если r < pos, то к реальной сумме добавится (val * (r - l + 1)), а к сумме, рассчитываемой по указанной ранее формуле, — ничего. Чтобы расчётное значение соответствовало реальному, от всех элементов a1[] с индексами больше r нужно отнять (val * (r - l + 1)), то есть прибавить к ним (val * (l - 1 - r));

Можно видеть, что операции над массивом a1[] можно реализовать с помощью второго дерева Фенвика:

• Добавление значения val на отрезке l..r: updateA(l, val); updateA(r + 1, -val); updateA1(l, val * (l - 1)); updateA1(r + 1, -val * r);
• Подсчёт суммы на отрезке 1..r: sumA(r) * r - sumA1(r);

Ссылки

• topcoder.com — How to modify BIT to update the ranges and query the ranges?
• topcoder.com — Range update in BIT
• kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree