E-maxx_algo - Страница 36

Sqrt декомпозицията е метод или структура от данни, която ви позволява да извършвате някои типични операции (сумиране на елементите на подмасив, намиране на минимум/максимум и т.н.) за , които

много по-бързо, отколкото за тривиалния алгоритъм.

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

разделяне на входни заявки в sqrt блокове.

Структура на данните, базирана на sqrt декомпозиция

Да си поставим задача. Даден е масив

. Изисква се да се приложи структура от данни, която

ще може да намери сумата от елементи за произволни и операции.

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

Можем да приемем, че дължината на един блок и броят на блоковете са равни на едно и също число - корен от , закръглен нагоре:

тогава масивът се разделя на блокове по следния начин:

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

---