419
правок
Изменения
→Свойства
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
1) позволяет вычислять значение некоторой обратимой операции <tex>G </tex> на любом отрезке <tex>[L; R] </tex> за время <tex>O(\log N)</tex>;
2) позволяет изменять значение любого элемента за <tex>O(\log N)</tex>;
4) легко обобщается на случай многомерных массивов.
5) позволяет представить любой отрезок от i до j <tex>[L; R]</tex> в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
