Корневая декомпозиция (корнячка) - достаточно абстрактная идея оптимизации. Допустим дано \(n\) объектов с которыми как-то нужно манипулировать. Разделим их на блоки по \(C\) объектов. Допустим надо надо как-то обработать что-то вроде запроса, при котором мы обработаем не более \(O(C)\) объектов по отдельности и хоть все блоки, каждый за \(O(1)\).
Тогда асимптотика на запрос \(O(C+\frac{n}{C} )\). Давайте сделаем \(C = \sqrt{n}\). Тогда асимптотика на запрос \(O(\sqrt{n})\).
Этот раздел пока не заполнен
Допустим дано натуральных \(m\) чисел, в сумме дающих \(n\). Утверждается, что всего уникальных чисел \(O(\sqrt{n})\). Давайте сконструируем худший случай. Он будет выглядеть так: \(1,2,3...\). Сумма такого ряда растет квадратично (\( \frac{n*(n+1)}{2} \)). Следовательно если у нас есть такой ряд дающий в сумме \(n\), то длина ряда - \(O(\sqrt{n})\).
Это можно использовать в рюкзаке для оптимизации рюкзака до асимптотики \(O(n*\sqrt{n})\). Также если дано сколько-то строк суммарно не превосходящих по размеру \(n\), то уникальных размеров также будет \(O(\sqrt{n})\). Можно предподсчитать для каждой длины какую-нибудь интересную статистику (например хеши) и использовать ее в дальнейшем.
Пускай есть \(q\) запросов изменений и подсчета какой-то величины. Допустим мы умеем предподсчитывать за \(O(n)\) что-то полезное, а потом быстро отвечать, без учета запросов изменений. Тогда давайте научимся с учетом запросов изменений также быстро уточнять данные. Давайте будем сохранять все запросы изменения, и когда нужно ответить на запрос, будем брать предподсчитанные ранее данные и использовать сохраненные запросы. Каждый \(\sqrt{q}\) запросов будем делать предподсчет заново с учетом запросов изменений. Тогда когда нам нужно выдать информацию нам придется перебрать не более \(\sqrt{q}\) запросов изменений и \(\sqrt{q}\) раз мы перезапустим наш предподсчет. Итоговая асимптотика: \(O( (n + q)\sqrt{q})\)