Дерево відрізків — запити суми та мінімуму на діапазоні

← 🤖 Алгоритми та AI

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

Запити на діапазоні за O(log n)

Режим

Запит [L, R]

Точкове оновлення

Індекс

Значення

Статистика

Розмір масиву

Відвідано вузлів

Результат запиту

—

Режим

Сума

Довідка та теорія

Дерево відрізків — це бінарне дерево, побудоване над індексами масиву, де кожен вузол покриває суцільний діапазон. Листки покривають окремі елементи; кожен внутрішній вузол зберігає агрегат (суму або мінімум) свого діапазону, обчислений з двох його дочірніх вузлів.

Побудова за O(n)

Побудова знизу вгору (або через рекурсивний поділ «розділяй і володарюй») об'єднує n листків у ~2n вузлів загалом, виконуючи O(1) роботи на вузол — тобто O(n) загалом.

Запит на діапазоні за O(log n)

Запит [L,R] рекурсивно спускається в діапазон вузла: якщо він повністю поза [L,R] — пропускаємо; якщо повністю всередині — використовуємо заздалегідь обчислений агрегат вузла напряму; якщо частково перетинається — рекурсивно заходимо в обидва дочірні вузли. Загалом повністю комбінується щонайбільше O(log n) вузлів, оскільки діапазон запиту розкладається щонайбільше на два «ланцюжки» канонічних піддіапазонів на кожному рівні дерева.

Точкове оновлення за O(log n)

Оновлення одного елемента масиву робить недійсними лише O(log n) предків на шляху від цього листка до кореня; кожен з них перераховується з двох своїх дочірніх вузлів на шляху назад.

Чому не просто префіксні суми?

Префіксні суми відповідають на запит суми на діапазоні за O(1), але потребують O(n) для оновлення одного елемента і взагалі не підтримують запит мінімуму на діапазоні (мінімум не має оберненої операції). Дерево відрізків обмінює трохи швидкості запиту на швидкі оновлення та підтримку будь-якого асоціативного комбінатора.

Поза межами цієї симуляції

Лінива пропагація розширює дерева відрізків, щоб підтримувати O(log n) оновлення на діапазоні (а не лише точкові оновлення), відкладаючи незастосовані оновлення на піддеревах, доки вони справді не будуть відвідані.

Про цю симуляцію

Оновлено: 11 липня 2026 р.

Дерево відрізків — це бінарне дерево, побудоване над індексами масиву, у якому кожен вузол представляє суцільний діапазон і зберігає агреговане значення — суму, мінімум, максимум чи будь-яку іншу асоціативну комбінацію — цього діапазону, обчислене з його двох дочірніх вузлів. Побудова займає O(n) часу і приблизно від 2n до 4n вузлів для масиву з n елементів. Запит на діапазоні [L, R] рекурсивно спускається деревом, одразу використовуючи заздалегідь обчислений агрегат вузла, коли його діапазон повністю лежить усередині [L, R], пропускаючи діапазони, що повністю поза ним, і заходячи в дочірні вузли лише за часткового перетину; це торкається щонайбільше O(log n) вузлів, оскільки запит розкладається на обмежену кількість канонічних піддіапазонів на кожному рівні. Точкове оновлення потребує перерахунку лише O(log n) предків на шляху від зміненого листка до кореня. Порівняно з префіксними сумами, які відповідають на запит суми за O(1), але вимагають O(n) для оновлення елемента і взагалі не підтримують запит мінімуму на діапазоні, дерево відрізків обмінює невелику константну вартість запиту на оновлення за O(log n) та підтримку будь-якого асоціативного оператора.

🔬 Що це показує

Симуляція будує дерево відрізків над масивом з десяти елементів і візуалізує, які вузли беруть участь у кожній операції. Листкові вузли (внизу дерева) відповідають окремим елементам масиву; кожен внутрішній вузол вище показує агрегат (суму або мінімум) свого діапазону. Під час запиту підсвічуються саме ті вузли, чиї діапазони повністю покривають [L, R] — і їх завжди щонайбільше O(log n), незалежно від розміру діапазону запиту.

🎮 Як користуватися

Оберіть режим «Сума» або «Мінімум», задайте діапазон [L, R] і натисніть «Запит», щоб побачити, які вузли комбінуються та який результат отримано. Введіть індекс і нове значення та натисніть «Точкове оновлення», щоб змінити один елемент масиву й побачити, як оновлення підіймається шляхом предків до кореня. Кнопка «Рандомізувати масив» генерує новий випадковий масив і перебудовує дерево з нуля.

💡 Чи знали ви?

Дерево відрізків з n елементів використовує приблизно 2n–4n вузлів, тобто лише константний коефіцієнт накладних витрат порівняно з вихідним масивом — і за це воно отримує O(log n) запити та оновлення замість O(n). Розширення на кшталт лінивої пропагації йдуть ще далі, дозволяючи оновлювати цілий діапазон за O(log n), а не лише один елемент.

Поширені запитання

Чому запит до дерева відрізків торкається лише O(log n) вузлів?

Будь-який діапазон запиту [L, R] можна розкласти щонайбільше на O(log n) «канонічних» діапазонів вузлів — на кожному рівні рекурсії межа запиту може розділити щонайбільше два вузли на часткові перетини, тоді як усе, що строго між цими межами, або повністю включене, або повністю виключене. Підсумовування цієї обмеженої роботи по всіх O(log n) рівнях дерева дає загальну вартість запиту O(log n).

Навіщо використовувати дерево відрізків замість префіксних сум для запитів на діапазоні?

Префіксні суми відповідають на запит суми на діапазоні за O(1), але вимагають O(n) роботи для оновлення одного елемента масиву, оскільки кожна префіксна сума після цього індексу має зміститися. Префіксні суми також взагалі не можуть відповідати на запити мінімуму на діапазоні, бо віднімання не має аналога для мінімуму. Дерево відрізків підтримує і точкові оновлення, і запити на діапазоні — для будь-якого асоціативного оператора — за O(log n).

Як точкове оновлення поширюється деревом?

Оновлення масиву за одним індексом змінює рівно один листок. Далі оновлення підіймається унікальним шляхом від цього листка до кореня, перераховуючи агрегат кожного предка як комбінацію поточних значень його двох дочірніх вузлів. Оскільки висота дерева O(log n), це торкається загалом O(log n) вузлів.

Скільки пам'яті використовує дерево відрізків?

Рекурсивне або масив-орієнтоване дерево відрізків над n елементами зазвичай використовує від 2n до 4n вузлів, залежно від реалізації (поширене масив-орієнтоване представлення виділяє 4n слотів, щоб безпечно охопити розміри, що не є степенем двійки, без ретельної індексації). Це константні накладні витрати порівняно з масивом вхідних даних розміром O(n) — невелика ціна за запити та оновлення за O(log n).