Первоначально опубликовано по адресу: rameshaditya.github.io/algorithmic-memoirs/traversing-segment-trees.html
Не спеша, это мой первый пост на Medium, я подумал, давай попробуем что-нибудь новенькое. Итак, приступим!
Хорошо! Итак, в конкурентном программировании существует мощная структура данных, называемая деревом сегментов (SegTree).
Он используется в основном для оптимизации запросов диапазона от O (n) до O (logn), где ’n’ относится к количеству элементов.
Рассмотрим этот пример -
Вам дан массив A из N чисел. Вам также задают Q-запросы. Каждый запрос имеет форму «L R» (без кавычек), и от вас требуется вернуть сумму значений от индекса L до индекса R.
Теперь нужно применить методику грубой силы. Но здесь также можно использовать дерево сегментов. Другой распространенной проблемой является проблема RMQ (запрос минимального диапазона), когда вам необходимо найти минимальное значение между заданным индексом L и R.
Итак, теперь мотивация учиться этому ясна. Деревья сегментов - это бинарные деревья, как следует из названия, и особое свойство дерева сегментов, которое делает его таким мощным, - это -
Каждый узел хранит результат своих дочерних узлов.
В одной строке, вот и все. Это большое дело.
Давайте решим проблему с запросом суммы диапазона (выделено курсивом выше)
Здесь конечными узлами segTree будут соответствующие значения в данном массиве.
Теперь рекурсивная реализация segTrees требует пространства 4 * N. Его построение занимает O (n * logn), поскольку к каждому элементу осуществляется доступ один раз, и для каждого элемента выполняется обход глубины дерева.
Рассмотрим массив A = {5, 3, 1, 8, 6, 7, 21, 9}
На диаграмме зеленые числа - это значения в segTree, синие числа - это индексы segTree (для удобства используйте индексирование на основе 1, поскольку дочерние элементы узла x равны 2 * x и 2 * x + 1) , цифры, разделенные красным дефисом, представляют собой диапазон предварительно обработанного решения (называемого диапазоном узлов).
Следовательно, построить это будет следующим образом -
int build(int node,int start,int end){
if(start==end)tree[node]=A[start];
else{
int mid=(start+end)>>1;
build(node<<1,start,mid);
build(node<<1|1,mid+1,end);
tree[node]=tree[node<<1]+tree[node<<1|1];
}
}
Как только вы это поняли, прочтите следующий фрагмент.
Принцип работы segTree заключается в том, что после того, как вам предоставляется запрос, он многократно разбивает запрос на диапазоны, для которых он может быть предварительно обработан, и когда диапазон узлов является подмножеством диапазона запроса, он возвращает значение в этом узле. В противном случае он снова разветвляется на обоих дочерних элементов.
Итак, давайте рассмотрим три типа перекрытия:
- Нет перекрытия
- Полное перекрытие
- Частичное перекрытие
Без перекрытия - диапазон узлов выходит за пределы диапазона запроса. Таким образом, вы видите здесь бесполезный узел. Делать нечего, идем дальше.
Полное перекрытие - диапазон узлов полностью находится внутри диапазона запроса. Это полностью действующий узел и очень полезный. Вернуть значение в этом узле.
Частичное перекрытие - часть этого диапазона узлов принадлежит диапазону запроса, поэтому выполняйте рекурсию для обоих дочерних узлов до тех пор, пока не будет «перекрытия нет» или «полного перекрытия».
Это алгоритм запроса.
Его реализация будет выглядеть следующим образом:
(Примечание: start и end здесь относятся к диапазонам узлов, а l и r соответствуют диапазону запроса. .)
int query(int node,int start,int end,int l,int r){
//No overlap
if(l>end || r<start)return 0;
//Total overlap
if(l<=start && end<=r)return tree[node];
//Partial overlap
else{
int mid=(start+end)>>1;
int a=query(node<<1,start,mid,l,r);
int b=query(node<<1|1,mid+1,end,l,r);
return a+b;
}
}
и так реализуется алгоритм запроса.
Один из моих любимых вопросов на SegTrees - Chef and Sub Array
Грубая сила принесет 30 точек, но SegTree получит 100 точек.
Теперь рассмотрим дополнение к вопросу. Предположим, от нас также требовалось обновить значение индекса 'idx' для A на значение 'val'. Затем вы должны необходимо реализовать метод точечного обновления.
Этот метод обновления точки будет очень похож на метод сборки. Основное отличие состоит в том, что случай частичного перекрытия необходимо изменить для вызова рекурсивной функции, только если idx находится между start и end (как вы пытаетесь найти этот индекс для обновления), и когда будет достигнут базовый вариант, A [idx] + = val; и tree [node] + = val;
Из-за рекурсивного характера функции все родительские элементы обновленного узла также обновятся.
Его реализация будет выглядеть следующим образом -
int update(int node, int start, int end, int val, int idx){
if(start==end){
tree[node]+=val;
A[idx]+=val;
}
else{
int mid=(start+end)>>1;
if(start<=idx && idx<=mid)
update(node<<1,start,mid,val,idx);
else
update(node<<1|1,mid+1,end,val,idx);
tree[node]=tree[2*node]+tree[2*node+1];
}
}
Сложность обновления также равна O (logn), поскольку необходимо пройти по глубине дерева.
Однако, если требуется обновление диапазона, сложность наихудшего случая метода обновления точки переходит в O (n * logn), что необходимо решить с помощью другого метода, называемого ленивое распространение, которое вы обнаружите подробно объяснил здесь. :)
По моему опыту, деревья сегментов - потенциальное решение, когда запросы-обновления диапазона необходимо выполнять оптимально, и тем более, когда функция коммутативна и ассоциативна. В любом случае, я надеюсь, что этот урок по деревьям сегментов был образовательным. Не стесняйтесь пинговать меня с любыми комментариями!
Адитья Рамеш
