Алгоритмы / [Из песочницы] Sqrt-декомпозиция (корневая оптимизация)

Sqrt-декомпозиция — это метод, или структура данных, позволяющая в режиме онлайн проводить такие операции, как подсчет суммы на отрезке за image и обновление элемента за image. Существуют более эффективные структуры, такие как дерево фенвика или дерево отрезков, которые оба запроса обрабатывают за image. Однако я хочу рассказать про корневую оптимизацию, т.к. в этом методе заложена идея, применимая к задачам другого типа.

Алгоритмы / [Из песочницы] Sqrt-декомпозиция (корневая оптимизация)

Постановка задачи

Пусть нам задан массив A[i], на который поступают запросы вида:

  • посчитать сумму на отрезке [L; R] (позже, мы поймем, что аналогично можно вычислять функции min, max, gcd и др.
  • добавить к элементу A[i], delta
Наивная реализация

Мы можем предрасчитать массив частичных сумм, а именно:

 for(int j = 0; j < i; j++) B[j] += A[i];

и тогда на запрос суммы [L; R], мы будем возвращать B[R]-B[L-1] за image. Однако на запрос изменения, потребует пересчета частичных сумм (содержащих этот элемент) и в худшем случае составит асимптотику порядка image, что не есть хорошо.

Рубрика: Habr