Inner Cycle Optimization

В тази секция ще разгледаме така наречената "оптимизация на вътрешния цикъл". Тя всъщност не е изобщо алгоритъм или нещо, което можете да "научите" как се прави, тъй като в различни задачи бива приложена по различен начин. Главната идея е да напишете наивно решение (или понякога не наивно, но все пак бавно), и да премахнете най-вътрешния цикъл на изчисленията, заменяйки го с една единствена операция (ползване на вече изчислена стойност, обхождане на елементите единствено по изпъкналата обвивка на някаква функция, или взимане на елемент от структура данни - опашка, стек, пирамида, индексно дърво или всъщност всякаква друга). Така оптимизирате бързодействието на решението си многократно (от O(X*N) на O(X), или на O(X*logN)). Сложното в този тип задачи е да се сетите каква структура данни да ползвате (и как), или да направите някакво наблюдение как можете да ползвате вече намерени стойности.

Тук би ви била полезна темата за Сегментни Дървета.

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