Формальное определение: Дерево сегментов — это структура данных, которая может хранить информацию о любом сегменте (подмассиве) [i..j] массива Arr[начало…конец] и позволяет нам извлечь этот информацию и обновлять ее за логарифмическое время.
Напуганы формальным определением ?? :)(Если ответ положительный -› не волнуйтесь. Это всего лишь означает, что вы такие же, как я.)
Начнем наше путешествие в мир Segment Tree с истории:
Есть два друга: Алиса и Боб.
Алиса и Боб учатся в одном классе. Это свободное время, и они решают поиграть в игру. Алиса придумывает уникальную игру. Условия игры такие:
- Алиса будет выкрикивать поток чисел -› [n1,n2,n3,n4,n5,n6,n7,n8,….], где ni — число от 1 до 100
- Боб должен записать эти числа, и как только Алиса закончит, начнется игра.
- Алиса будет задавать вопросы Бобу, и он должен отвечать на вопросы как можно быстрее.
Запросы будут в таком формате:
q(1,5) -›что означает, что Боб должен найти n1+n2+n3+n4+n5 и сказать ответ Алисе.
q(7,13) означает n7+n8+n9+n10+n11+n12+n13
q(5,8) означает n5+n6+n7+n8
4. Алиса задаст 3 вопроса Бобу, она запишет общее время, которое потребуется Бобу, чтобы ответить на все 3 запроса.
5. После 3 запросов Боб задаст 3 запроса Алисе и запишет общее время, затраченное Алисой на ответы на все запросы.
6. Выигрывает тот, кто потратит меньше времени.
ПРИМЕЧАНИЕ. Поскольку Алиса и Боб учатся в одном классе, им обоим требуется одна единица времени для выполнения любой операции сложения или вычитания.
ПЕРВЫЙ РАУНД
Алиса произносит поток из 9 чисел: 3,5,4,7,2,8,1,9,6, а числа имеют вид: n0 = 3, n1 = 5, n2 = 4 и так далее. .
Боб записывает это, и вот первый запрос:
Запрос 1: q(3,5)
Боб выполняет сложение следующим образом:
n3 +n4 +n5 = 7 + 2 + 8 = 17
Боб отвечает, и общее время составляет 2 единицы (1 за 7 + 2 = 9 и 1 за 9 + 8 = 17).
Общее время, затраченное Бобом на данный момент = 2 единицы
Запрос 2: q(4,7)
Боб выполняет сложение следующим образом:
n4 +n5 + n6 + n7 = 2 + 8 + 1 + 9 = 20
Боб отвечает, и общее время составляет 3 единицы (1 за 2 + 8 = 10, 1 за 10 + 1 = 11 и 1 за 11+9 = 20).
Общее время, затраченное Бобом на данный момент = 2 +3 = 5 единиц
Запрос 3: q(1,8)
Боб выполняет сложение следующим образом:
n1 +n2 + n3 + n4 + n5 +n6 + n7 + n8 = 5+4+7+2+8+1+9+6 = 42
Боб отвечает, и общее время составляет 7 единиц (поскольку он должен выполнить 7 сложений).
Общее время, затраченное Бобом на данный момент = 2 + 3 + 7 = 12 единиц
Следовательно, раунд 1 завершен, и общее время, затраченное Бобом, составляет 12 единиц.
ВТОРОЙ РАУНД
Боб действительно отчаянно хочет выиграть, и он хочет, чтобы Алисе было как можно сложнее отвечать на его вопросы.
Он говорит потоком из 15 цифр: 1,5,9,6,7,4,3,6,2,1,8,6,5,4,7
Алиса знает, что Боб пытается просто выиграть, задавая запросы в очень большом диапазоне. Она снова сообразительна и находит решение.
Еще до того, как Боб успел задать свой первый вопрос, она рисует странную картинку, подобную этой:
Алиса очень умно нарисовала такую картинку.
Сначала эта картинка выглядит очень странно, но если внимательно присмотреться, то можно узнать, что Алиса сделала.
Мы можем расшифровать изображение Алисы следующим образом:
Теперь Боб начинает задавать вопросы,
Запрос 1: q(3,12)
Алиса смотрит на свою картинку и выбирает следующие узлы:
Если мы внимательно посмотрим на картинку, то сможем узнать, что обозначают a, b, c и d:
a = n3
b = n4 +n5 + n5 +n6+n7
c= n8 + n9 + n10 + n11
d= n12
Следовательно, a + b + c + d = n3 + n4 +n5 + n5 +n6+n7 + n8 + n9 + n10 + n11 + n12
Используя этот подход, Алиса выполняет сложение следующим образом:
a + b + c + d (помните, как Боб выполнял сложение -> n1 + n2 +.. )
a + b+ c+ d = 6 + 20+ 17 +5 = 48, что по существу равно sum(n3,n12)
Следовательно, Алиса отвечает на первый запрос за 3 единицы времени.
Общее время, затраченное Алисой = 3 единицы
Запрос 2: q(0,14)
Алиса смотрит на свою картинку и выбирает следующие узлы:
На приведенном выше рисунке мы видим, что указанный выше узел представляет собой сумму всех узлов n0..n15.
Следовательно, Алиса отвечает на запрос за 1 единицу времени.
Общее время, затраченное Алисой = 3 + 1 = 4 единицы
Запрос 3: q(4,11)
Алиса смотрит на свою картинку и выбирает следующие узлы:
Мы знаем, что :
a = n4 +n5+ n6 +n7
b = n8 + n9 + n10+ n11
Следовательно, a+b будет ответом, и Алиса ответит правильно = a+ b = 20 + 17 = 37 всего за 1 единицу времени.
Общее время, затраченное Алисой = 4 + 1 = 5 единиц
ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ
Общее время, затраченное Бобом = 12 единиц
Общее время, затраченное Алисой = 5 Единиц
Давайте проанализируем общий диапазон запросов для Боба и Алисы:
Дело Боба:
q1(3,5) -> 3 элемента
q2(4,7) -> 4 элемента
q3(1,8) -› 8 элементов
Общий охват = 3 + 4 + 8 = 15 элементов
Общее время, затраченное на ответ = 12 единиц
Дело Алисы:
q1(3,12) -> 10 элементов
q2(0,14) -> 15 элементов
q3(4,11) -› 8 элементов
Общий охват = 10 + 15 + 8 = 33 элемента
Общее время, затраченное на ответ = 5 единиц
Диапазон Алисы более чем в два раза превышает интервал Боба, но время, затрачиваемое Алисой, составляет почти одну треть по сравнению с Бобом.
Это потрясающее улучшение производительности.
Только представьте, какая может быть разница в производительности, если нам разрешено задавать запросы в диапазоне [0,1000000000] :)
ЗАКЛЮЧЕНИЕ
Дерево, представленное на рис. 2, на самом деле является деревом сегментов. Это очень важная структура данных, когда речь идет озапросах на основе диапазонов.
Вы уже видели ее важность для повышения производительности в случае запросов на основе диапазонов. система.
Это всего лишь вводная статья о деревьях сегментов, и мы продолжим наше путешествие по изучению архитектуры и реализации дерева сегментов в следующих частях этой серии статей о дереве сегментов.
