Дерево Фенвика с модификацией на отрезке
Запрос отдельных элементов и модификация на отрезке
Если в задаче требуется производить изменения на отрезке и возвращать значения отдельных элементов, то пусть массив 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);