3622
правки
Изменения
м
→Метод «толстых» узлов
[[Файл:Список версий1.png|500px|центр]]
Пусть нужно сделать запрос ко второй версии структуры данных (на рисунке выше это запрос <tex>X.a-?)</tex>. Чтобы сделать этот запрос , нужно зайти в узел <tex>X</tex> и найти в списке версий максимальную версию, которая меньше или равна версии запроса (в примере на рисунке это версия <tex>2</tex>), и в этой версии узла найти значение поля <tex>a</tex> (в примере <tex>a=4</tex>).
Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.
