2.2. Дерево відрізків.
Означення 2.6 Дерево відрізків - це структура даних,
створена для роботи з такими інтервалами на числовій осі, кінці яких належать
фіксованій множині із N абсцис (ці абсциси можна
нормалізувати, заміняючи кожну із них її порядковим номером при обході їх зліва
на право). Можна вважати ці абсциси цілими числами на інтервалі [1,N].
Дерево відрізків - це двійкове
дерево з коренем. Для заданих цілих чисел l і r таких, що l< r, дерево відрізків
T(l,r) будується рекурсивно таким чином :
- Складається із кореня v з параметрами B[v]=l та E[v]=r; (B-Begin,E-End).
- Якщо r-l>1, то воно складається із лівого
піддерева
та правого піддерева
. ( Корені піддерев природно
позначити через ЛСИН[v] та ПСИН[v]
відповідно).
- Параметри B[v] та E[v]
позначають інтервал
, зв'язаний
з вузлом v.
Інтервали, що належать
множині {[B[v], E[v]]: v - вузол T(l, r)}, називаються
стандартними інтервалами дерева T(l, r).
Стандартні інтервали, які належать листам <span class='eq">T(l, r),
називаються елементарними інтервалами. T(l, r)
збалансоване і має глибину 
.
Мал.. 1.1. Дерево відрізків T(4, 15)
Алгоритм
вставки інтервалу [b,e]
Фрагментація інтервалу [b,e] повністю визначається операцією, яка вставляє [b,e] в дерево відрізків Т, і зверненням ВСТАВИТИ
(b,e; корінь (Т)) до наступної процедури:
Procedure
ВСТАВИТИ (b, e; v)
begin if ( b <= B[v] ) and ( E[v] <= e) then призначити [b, e]
вузлу v
else begin if (
)
then
ВСТАВИТИ ( b, e; ЛСИН[v] );
if (
)
then
ВСТАВИТИ ( b, e; ПСИН [v] )
end
end
Дія ВСТАВИТИ ( b,
e; корінь ( Т ) ) відповідає "маршруту" в Т , який
має загальну структуру (мал.1.2):
- початковий шлях Рпоч. від кореня до вузла v*, який називається
розгалуженням, із якого виходять два шляхи - Р Л і Р П .
- інтервал, що вставляється відноситься або повністю до розгалуження, або до
усіх правих синів шляху РЛ та Р П ; при цьому визначається фрагментація [b,e] (вузли віднесення).
Procedure
ВИЛУЧИТИ (b, e; v)
begin if ( b <= B[v] ) and ( E[v] <= e) then
C[v]:=C[v]-1.
else begin if (
)
then
ВИЛУЧИТИ ( b, e; ЛСИН[v] );
if (
)
then
ВИЛУЧИТИ ( b, e; ПСИН [v] )
end
end
Мал. 1.2. Вставка інтервалу [74, 107] в T(1,257).Вузли
віднесення оточені двічі.