Минимум в интервал

Range Minimum Query

Като продължение на темата за Сегментни Дървета тук ще разгледаме как можем да ги ползваме като RMQ - структура, с която можем бързо да намираме минималния (или максималния) елемент в интервал от даден списък с числа, като можем и да променяме въпросните числа.

Автор: Александър Георгиев

Понякога вместо сума се налага да можем бързо да намираме минимум или максимум в под-интервал от даден масив с числа, или други обекти, които имат някаква наредба.

!	Тъй като намирането на минималния елемент е почти абсолютно същото като намиране на максимума (просто в кода трябва да заменим `min()` с `max()`), в примерите в тази тема ще разглеждаме само Range Minimum Query - тоест минимум.

Абстрактната структура, която поддържа тези операции, се нарича Range Minimum Query, и най-често ще срещнете с нейната абревиетура RMQ. Ако структурата позволява и бърза промяна на елементите, тогава става дума за динамично RMQ.

Има няколко популярни имплементации на тази абстрактна структура данни (водещи до различни сложности). На практика, много рядко се иска оптималната сложност (O(N) за строене и O(1) за питане); или пък трябва да се поддържа и ъпдейт (в който случай горните сложности са невъзможни). В тази тема ще разгледаме имплементация, базирана на сегментни дървета, която всъщност е много подобна на това, което вече разгледахме.

Поддържани операции и сложности

Поддържаните операции и техните сложности са стандартните за сегментните дървета:

O(N) за строене от N елемента;
O(log(N)) за променяне на елемент;
O(log(N)) за намиране на най-малкия елемент в даден интервал.

Идея

Всичко друго е същото като при сегментните дървета, които вече разгледахме, с изключение на това, че сега бащите ще пазят минимума на децата си, вместо сумата им.

Нека, например, имаме масив с 13 елемента със стойности (42, 13, 17, 1, -18, 3, -2, 9, 22, 4, 19, -23, 12). RMQ-то, пазещо информацията за този масив, би изглеждало по следния начин:

В паметта това дърво би било масив с 27 елемента:
(неизползван, -23, -18, -23, 1, -18, -23, 12, 13, 1, -18, -2, 4, -23, 12, 0, 42, 13, 17, 1, -18, 3, -2, 9, 22, 4, 19, -23, 12)

Промяна на елемент

За да променим стойността на даден елемент, първо променяме листото на сегментното дърво, което отговаря за този елемент, след което тръгваме нагоре по дървото и правим всеки връх да е равен на минимума от двете си деца. Продължаваме това докато стигнем до корена.

Тъй като дървото е идеално балансирано, неговата дълбочина е точно log(N), и съответно сложността на тази операция е O(log(N)). Можем допълнително да забързаме тази процедура, като спрем в момента, в който не променим даден връх (тоест той вече съдържа стойността на по-малкото си дете).

Примерен код, който имплементира това:

void
 update(int
 idx,
 int value) {
    idx +
=
 (TREE_SIZE >
>
 1
);
    tree[idx] =
 value;
    for
 (idx =
 idx >
>
 1
;
 idx >
 0
;
 idx >
>
=
 1)
        tree[idx] =
 min(tree[(idx <
<
 1
) +
 0
],
 tree[(idx <
<
 1
) +
 1
]);
}

Нека разгледаме как би се променило дървото, ако променим елемента с индекс четири от -18 на 5. Ъпдейтвайки дървото нагоре, се получава следното:

Ако забелязвате, след като обновим всички върхове по пътя до корена нагоре по дървото, структурата отново има вида, който искахме: върховете в най-долното ниво пазят текущите стойности на масива, а всеки връх от по-горните нива пази минимума на децата си.

Търсене

Търсенето на минимума в интервал [left, right] също е сходно на намирането на сума, което показахме. Разбира се, този път вместо да сумираме поддърветата, ще вземаме минимума.

int
 query(int
 left,
 int right) {
    int
 idxL =
 left +
 (TREE_SIZE >
>
 1
);
    int
 idxR =
 right +
 (TREE_SIZE >
>
 1
);
    
    int
 res =
 min(tree[idxL],
 tree[idxR]);
    while
 (idxL +
 1
 < idxR) {
        if
 ((idxL &
 1
) =
=
 0
) res =
 min(res,
 tree[idxL ^
 1
]);
        if
 ((idxR &
 1
) =
=
 1
) res =
 min(res,
 tree[idxR ^
 1
]);
        idxL >
>
=
 1
,
 idxR >
>
=
 1
;
    }
    return
 res;
}

Вижте следния пример за намиране на минимума сред числата в интервала [1, 10] (от 13 до 19):

!	Цялата идея на сегментните дървета е да обработват бързо възможно по-големи поддървета, които изцяло попадат в интервала (`left`, `right`). Пример за такива поддървета са тези, чиито корени са оцветени в синьо.

Червените върхове са тези, от които започваме. Черните са тези, през които минават idxL и idxR. Сините са корените на поддърветата, които обработваме без да обхождаме рекурсивно. Припомняме, че това са десните братя на idxL и левите братя на idxR.

Можем да се убедим, че min(13, 1, -18, 4, 19) = -18 наистина е минималният елемент сред (13, 17, 1, -18, 3, -2, 9, 22, 4, 19).

Строене

Строенето на RMQ (базирано на сегментни дървета) от N елемента става като първо сетнем стойностите на листата (които са просто стойностите на дадения ни списък с числа), а след това обходим горните нива и ги направим да са равни на минимумите на децата си:

void
 buildTree(int
*
 values,
 int valueCount) {
    memset(tree,
 63
,
 sizeof
(tree));
 // Initializes with a value > 1,000,000,000
    for
 (int
 i =
 0
;
 i <
 valueCount;
 i+
+)
        tree[i +
 (TREE_SIZE >
>
 1
)] =
 values[i];
    for
 (int
 node =
 (TREE_SIZE >
>
 1
) -
 1
;
 node >
 0
;
 node-
-)
        tree[node] =
 min(tree[(node <
<
 1
) +
 0
],
 tree[(node <
<
 1
) +
 1
]);
}

Двумерни и многомерни RMQ-та

И тук няма проблем да имаме двумерни или многомерни дървета (и, съответно, RMQ-та). Сложността от O(log(N)∙log(M)) за куери и ъпдейт се запазва. Този път няма да показваме имплементация, тъй като е напълно аналогична с това, което показахме в темата за сегментни дървета.

Пълна имплементации

Предоставяме пълна имплементация с тестер:

Динамично RMQ (сегментни дървета)

Задачи за тренировка

Можете да напишете чистата форма на структурата за да решите тренировъчната задача

RMQ

Training problems, informatika.bg

Author: Alexander Georgiev
Tags: Medium, RMQ, Segment Trees
Statement | Archive | Online Judge

RMQ.

Едно от възможните решения на задачата Rain също е базирано на RMQ.

Задачата Travel пък се решава чрез динамично оптимиране с оптимизация на вътрешния цикъл, което ще разгледаме в тази тема. В този случай оптимизацията на вътрешния цикъл ползва RMQ за да намери най-добрият отговор надолу и надясно от всяка бензиностанция.

Референции

Сегментни Дървета (www.informatika.bg)

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 3767 пъти.