Дерево відрізків

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У інформатиці, 'дерево відрізків' це деревоподібна структура даних яка застосовується для зберігання даних у відрізках, згрупованих так, що відомо, які з них містять дану точку. Така структура дозволяє ефективно (за кількість операцій порядку O (log n)) реалізувати операції з даними одразу з усього відрізка, наприклад: знаходження суми/мінімуму з елементів масиву в заданому відрізку ([l,r], де l і r надходять на вхід алгоритму). При цьому можлива модифікація елементів масиву: як зміна значення одного елемента , так і зміна елементів на цілому підінтервалі масиву (тобто дозволяється присвоїти всім елементам відрізку [l, r] якесь значення, або додати до всіх елементів цього відрізку якесь число).

Дерево відрізків - дуже гнучка структура, і число завдань, що вирішуються за її допомогою величезне. Крім наведених операцій з деревами відрізків, можливі і набагато більш складні. Також дерево відрізків легко узагальнюється і на більші розмірності: наприклад, для вирішення завдання про пошук суми/мінімуму в деякому прямокутнику даної матриці (щоправда, вже тільки за час O (log² n)). Дерево відрізків можна розглядати як різновидність червоно-чорного дерева [1] (стр. 375).

Важливою особливістю дерева відрізків є те, що воно споживає лінійний об'єм пам'яті.

Джерела інформації[ред.ред. код]

  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. / Под ред. И. В. Красикова (2005). Алгоритмы: построение и анализ = Introduction to Algorithms (рос. ) (вид. 2-ге). М.: Вильямс. с. 1296. ISBN 5-8459-0857-4.