Структуры данных

На практике часто возникают задачи, в которых приходится работать с динамически изменяющимися данными. Дерево Фенвика является структурой данных, позволяющей достаточно эффективно выдавать ответы на запросы о частичных суммах на различных отрезках массива, элементы которого могут меняться в процессе работы.

Пусть задан массив A из N чисел: A₀, A₁, ..., A_{N - 1}. Дерево Фенвика -- это структура данных, позволяющая выполнять две операции:

• rsq(i, j) -- выдать сумму элементов массива A с i-го по j-й включительно (rsq является сокращением от range sum query);
• update(k, d ) -- прибавить к k-му элементу массива A некоторое число d.

При простейшей реализации rsq(i, j) работает за время O(j - i + 1), что в общем случае составляет порядка O(N), а update(k, d ) -- за O(1). Для ответа на запрос rsq(i, j) достаточно в цикле просуммировать указанный отрезок массива, а при выполнении операции update(k, d ) -- изменить k-й элемент A_k.

Заметим однако, что при большом количестве запросов вида rsq(i, j) простейшая реализация не слишком эффективна, так как в общем случае ответ на каждый запрос требует времени, зависящего линейно от длины массива.

Дерево Фенвика позволяет существенно сократить это время, поскольку выполняет каждую из указанных операций за время O(log N).