== Определение =='''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые типичные ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>.
== Описание ==
''Привидем описание для операции минимума''Пусть дан массив <tex>a[0 \ldots n-1]</tex>. Cделаем следующий предпосчёт: разделим массив A на блоки длины <tex>len = \lfloor \sqrt{n} \rfloor</tex> , и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков:
Дан массив <tex>A[0 \underbrace{a_0, a_1, \ldots na_{len -1]</tex>. Cделаем следующий предпосчёт: разделим массив A на блоки длины <tex>}}_{b_0}, \ldots \sqrtunderbrace{na_{len}</tex> (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть \ldots a_{2 len — это длина блока <tex>(len \approx \sqrt- 1}}_{nb_1})</tex>, а <tex>cnt = \leftldots \lceil underbrace{a_{(cnt - 1) len} \fracldots a_{n-1}}_{lenb_{cnt - 1}} \right\rceil</tex> — количество блоков:
[[Файл:Корневая эвристикаЧерез <tex>b_k</tex> обозначим результат предпосчёта в k-ом подотрезке.png]]
Через <tex>b_k</tex> мы обозначили результат предпосчёта в k-ом подотрезке.Приведем описание для операции минимума:=== Запрос ===
Пусть мы получили запрос на извлечение минимума на отрезке <tex> [l \ldots r] </tex>. Отрезок может охватить некоторые блоки <tex> b </tex> полностью, и не более двух блоков (начальный и конечный) {{---}} не полностью. Проверка на то, что начальный блок вошел в отрезок не полностью, осуществляется как <tex> l \mod len \neq 0 </tex>. Конечный блок проверяется как <tex> (r + 1) \mod len \neq 0 </tex>. Для того чтобы найти минимум на отрезке <tex>[l \ldots r]</tex>, надо найти минимум среди элементов в "хвостовнеполных блоках": <tex>[l \ldots (k+1)len-1]</tex> и <tex>[(p+1)len \ldots r]</tex>, и минимума среди <tex>b_i</tex> во всех блоках, начиная с k и заканчивая p:
<tex>\min_{i = l}^r a_i = \min(\min_{i = l}^{(k + 1)len - 1}(a_i),\min_{i = k}^p( b_i),\min_{i = p + 1}^r (a_i))</tex>
=== Изменение элемента ===
Теперь разрешим изменять элементы. Если меняется какой-то элемент <tex>a_i</tex>, то достаточно пересчитать значение <tex>b_k</tex> в том блоке, в котором этот элемент находится:
