Матеріал з Вікіконспекти
Дерево відрізків (англ. Segment tree) - це структура даних, яка дозволяє за асимптотику реалізувати будь-які операції, що визначаються на безлічі, на якому дана операція асоціативна, і існує нейтральний елемент відносно цієї операції, тобто на моноїд. Наприклад, підсумовування на безлічі натуральних чисел, пошук мінімуму на будь-якому числовому безлічі, множення матриць на безлічі матриць розміру, об'єднання множин, пошук найбільшого загального дільника на множині цілих чисел і многочленів.
При цьому додатково можлива зміна елементів масиву: як зміна значення одного елемента, так і зміна елементів на цілому подотрезке масиву. наприклад дозволяється привласнити всім елементам будь-яке значення, або додати до всіх елементів масиву якесь число. Структура займає пам'яті, а її побудова вимагає часу.
[Ред] Структура
Структура являє собою дерево, листям якого є елементи вихідного масиву. Інші вершини цього дерева мають по 2 дитини і містять результат операції від своїх дітей (наприклад мінімум або суму). Таким чином, корінь містить результат шуканої функції від усього масиву, лівий дитина кореня містить результат функції на, а правий, відповідно результат на. І так далі, просуваючись вглиб дерева.
[Ред] Побудова дерева
Нехай вихідний масив складається з елементів. Для зручності побудови збільшимо довжину масиву так, щоб вона дорівнювала найближчій ступеня двійки, тобто , Де. Це зроблено, для того щоб не допустити звернення до неіснуючих елементів масиву при подальшому процесі побудови. Порожні елементи необхідно заповнити нейтральними елементами моноїд. Тоді для зберігання дерева відрізків знадобиться масив з елементів, оскільки в гіршому випадку кількість вершин в дереві можна оцінити сумою, де. Таким чином, структура займає лінійну пам'ять.
Процес побудови дерева полягає в заповненні масиву. Заповнимо цей масив таким чином, щоб -й елемент був би результатом деякої бінарної операції (для кожного конкретного завдання своєї) від елементів c номерами і, тобто батько був результатом бінарної операції від своїх синів. Один з варіантів - робити рекурсивно. Нехай у нас є вихідний масив, а також змінні і, що позначають межі поточного полуінтервала. Запускаємо процедуру побудови від кореня дерева відрізків (,,), а сама процедура побудови, якщо її викликали немає від листа, викликає себе від кожного з двох синів і підсумовує обчислені значення, а якщо її викликали від листа - то просто записує в себе значення цього елемента масиву (Для цього у нас є вихідний масив). Асимптотика побудови дерева відрізків складе, таким чином,.
Виділяють два основних способи побудови дерева відрізків: побудова знизу і побудова зверху. При побудові знизу алгоритм піднімається від листя до кореня (Просто починаємо заповнювати елементи масиву від більшого індексу до меншого, таким чином при заповненні елемента його діти і вже будуть заповнені, і ми з легкістю порахуємо бінарну операцію від них), а при побудові зверху спускається від кореня до листя. Особливі зміни з'являються в реалізації запитів до таких деревах відрізків.
Реалізація побудови зверху:
Реалізація побудови знизу: