ДФ

Как я и говорил, сегодня я расскажу про дерево Фенвика(далее ДФ). ДФ - структура данных, позволяющая отвечать на запросы на отрезках, преимущественно на сумму(этот случай мы и будем далее рассматривать). ДФ представляет из себя массив длины n, где t[i] - сумма на отрезке a[f(i):i], где f(i) - некоторая функция, что f(x)<=x, обычно f(x) = x&(x+1), тк в таком случае запрос будет производиться за O(log n). Чтобы найти сумму на отрезке [0:r] найдём сумму t[r]+t[f(r)-1]+t[f(f(r)-1)-1]+...

Чтобы найти сумму на отрезке [l:r], просто вычислим сумму на [0:r]-сумма на [0:(l-1)]. Сообственно для обычного ДФ всё, пишется и работает быстро, хоть и только для суммы.

Также особенность ДФ - лёгкое обобщение для больших размерностей, собственно создаём ДФ из ДФов и всё.