Корневая декомпозиция (sqrt decomposition): блоки √n, сумма и минимум на отрезке
Корневая декомпозиция простыми словами: блоки размера √n, сумма и минимум на отрезке с обновлениями, прибавление на отрезке, сравнение с деревом отрезков и Фенвиком. Код на Python.
Коротко
| Операция | Корневая декомпозиция | Дерево отрезков |
|---|---|---|
| Построение | O(n) | O(n) |
| Запрос на отрезке (сумма, минимум) | ||
| Изменение одного элемента | O(1) для суммы, для минимума | |
| Прибавление на отрезке | с ленивыми метками | |
| Память |
- Режем массив на блоки по элементов и для каждого блока храним готовый ответ: сумму, минимум, отсортированную копию.
- Любой отрезок
[l, r]— это хвост одного блока, несколько целых блоков и начало другого блока. Хвосты проходим поэлементно, целые блоки берём из кэша. - Асимптотика хуже, чем у дерева отрезков, зато код пишется за пять минут и легко подстраивается под нестандартные запросы.
Задача
Дан массив a из n чисел. Приходят запросы двух типов:
update(i, value)— присвоитьa[i] = value;query(l, r)— посчитать сумму (или минимум) на отрезкеa[l..r]включительно.
Запросов q штук, n и q — до .
Наивных решений два, и оба плохие:
- Хранить массив как есть. Обновление за O(1), запрос — проход по отрезку за O(n). На запросов это до операций.
- Хранить префиксные суммы. Запрос за O(1), но одно обновление ломает все префиксы правее
i, и пересчёт стоит O(n).
Одна операция дешёвая, другая — линейная. Корневая декомпозиция находит компромисс: обе операции за .
Идея: блоки размера √n
Разобьём массив на блоки по B элементов. Блоков получится . Для каждого блока заранее посчитаем сумму его элементов.
Возьмём массив из 9 элементов, :
индекс: 0 1 2 | 3 4 5 | 6 7 8
a: 5 2 8 | 1 9 3 | 7 4 6
блок: 0 | 1 | 2
sums: 15 | 13 | 17
Элемент с индексом i лежит в блоке i // B. Блок k занимает индексы от k * B до (k + 1) * B - 1; последний блок может оказаться короче.
Теперь запрос суммы на [1, 7]:
индекс: 0 [1 2 | 3 4 5 | 6 7] 8
^^^^ ^^^^^^^ ^^^^
хвост целый начало
блока 0 блок 1 блока 2
- хвост блока 0:
a[1] + a[2] = 2 + 8 = 10— поэлементно; - блок 1 целиком:
sums[1] = 13— из кэша, одна операция; - начало блока 2:
a[6] + a[7] = 7 + 4 = 11— поэлементно.
Итого 10 + 13 + 11 = 34.
Почему именно √n
Посчитаем стоимость запроса. Неполных кусков два, в каждом не больше B элементов. Целых блоков не больше n / B. Значит, запрос стоит порядка
Если B маленький, много целых блоков. Если большой, долго идти по хвостам. Сумма минимальна, когда слагаемые одного порядка: . Тогда обе части — , и весь запрос тоже . Отсюда и название: корень из n.
Для это блоки по 316 элементов, и запрос делает около тысячи простых операций вместо ста тысяч.
Сумма на отрезке: реализация
import math class SqrtSum: def __init__(self, a): self.a = list(a) n = len(self.a) self.b = max(1, math.isqrt(n)) # размер блока self.sums = [0] * ((n + self.b - 1) // self.b) for i, x in enumerate(self.a): self.sums[i // self.b] += x def update(self, i, value): # a[i] = value self.sums[i // self.b] += value - self.a[i] self.a[i] = value def query(self, l, r): # сумма a[l..r] включительно b = self.b res = 0 bl, br = l // b, r // b if bl == br: # отрезок внутри одного блока return sum(self.a[l:r + 1]) res += sum(self.a[l:(bl + 1) * b]) # хвост левого блока for k in range(bl + 1, br): # целые блоки res += self.sums[k] res += sum(self.a[br * b:r + 1]) # начало правого блока return res s = SqrtSum([5, 2, 8, 1, 9, 3, 7, 4, 6]) print(s.b, s.sums) # 3 [15, 13, 17] print(s.query(1, 7)) # 34 s.update(4, 0) # 9 -> 0, сумма блока 1: 13 -> 4 print(s.query(1, 7)) # 25
Обратите внимание на update: сумму блока не нужно пересчитывать заново, достаточно поправить её на разницу value - a[i]. Поэтому обновление работает за O(1).
Отдельная ветка для bl == br обязательна. Без неё отрезок внутри одного блока посчитался бы дважды: и как «хвост», и как «начало».
Минимум на отрезке
Запрос устроен так же, только вместо + — min. Разница в обновлении: минимум нельзя поправить на дельту. Если мы увеличили элемент, который и был минимумом блока, новый минимум может оказаться где угодно в блоке. Поэтому блок пересчитывается целиком — за .
import math class SqrtMin: def __init__(self, a): self.a = list(a) n = len(self.a) self.b = max(1, math.isqrt(n)) self.mins = [min(self.a[k:k + self.b]) for k in range(0, n, self.b)] def update(self, i, value): self.a[i] = value k = i // self.b start = k * self.b # минимум нельзя «поправить на дельту» — пересчитываем блок целиком self.mins[k] = min(self.a[start:start + self.b]) def query(self, l, r): b = self.b bl, br = l // b, r // b if bl == br: return min(self.a[l:r + 1]) res = min(self.a[l:(bl + 1) * b]) res = min(res, min(self.a[br * b:r + 1])) for k in range(bl + 1, br): res = min(res, self.mins[k]) return res
Обе операции — . Тот же шаблон подходит для максимума, НОД, побитового OR — для любой операции, которую можно посчитать по блоку и потом объединить.
Если обновлений нет вовсе, минимум на отрезке лучше искать через разреженную таблицу за O(1) на запрос.
Прибавление на отрезке
Усложним задачу: теперь обновление — «прибавить x ко всем элементам a[l..r]», а запрос — по-прежнему сумма на отрезке.
Если прибавлять поэлементно, обновление снова станет O(n). Решение — та же тройка «хвост, целые блоки, начало», но для целых блоков мы не трогаем элементы, а ставим отложенную метку add[k]: «ко всем элементам блока k прибавлено столько-то».
- В неполных кусках меняем элементы напрямую и правим
sumsблока. - Целым блокам увеличиваем только
add[k]. - В запросе реальное значение элемента —
a[i] + add[k], а реальная сумма целого блока —sums[k] + add[k] * длина_блока.
import math class SqrtRangeAdd: def __init__(self, a): self.a = list(a) n = len(self.a) self.b = max(1, math.isqrt(n)) m = (n + self.b - 1) // self.b self.sums = [0] * m self.add = [0] * m # отложенная прибавка к блоку for i, x in enumerate(self.a): self.sums[i // self.b] += x def _block_len(self, k): return min(self.b, len(self.a) - k * self.b) def range_add(self, l, r, x): # a[l..r] += x b = self.b bl, br = l // b, r // b if bl == br: for i in range(l, r + 1): self.a[i] += x self.sums[bl] += x * (r - l + 1) return for i in range(l, (bl + 1) * b): self.a[i] += x self.sums[bl] += x * ((bl + 1) * b - l) for k in range(bl + 1, br): self.add[k] += x # целый блок — только метка for i in range(br * b, r + 1): self.a[i] += x self.sums[br] += x * (r - br * b + 1) def query(self, l, r): b = self.b bl, br = l // b, r // b if bl == br: return sum(self.a[l:r + 1]) + self.add[bl] * (r - l + 1) res = sum(self.a[l:(bl + 1) * b]) + self.add[bl] * ((bl + 1) * b - l) for k in range(bl + 1, br): res += self.sums[k] + self.add[k] * self._block_len(k) res += sum(self.a[br * b:r + 1]) + self.add[br] * (r - br * b + 1) return res
Это прямой аналог ленивого распространения в дереве отрезков, только уровней не log n, а два: элемент и блок. Поэтому код короче и в нём сложнее ошибиться.
Важная деталь — _block_len. Последний блок бывает неполным, и если умножать add[k] на B, сумма выйдет больше реальной. В этом коде целые блоки идут строго между bl и br, поэтому последний блок туда не попадает, но функция страхует от ошибки, если вы перепишете обход.
Все три класса я проверял стресс-тестом: случайные массивы длиной от 1 до 60, по 200 случайных операций, сравнение с наивным пересчётом. Так стоит делать с любой самописной структурой, особенно перед тем как отправить решение.
Где корневая декомпозиция сильнее дерева отрезков
Пока что корень проигрывает по асимптотике. Его настоящая сила — в запросах, которые плохо ложатся на дерево.
Пример: «сколько элементов на отрезке [l, r] меньше x», с изменением элементов. В дереве отрезков пришлось бы хранить отсортированные списки в каждом узле (merge sort tree), а изменения в нём болезненны. С блоками всё просто: храним каждый блок отсортированным и ищем x бинпоиском.
import math from bisect import bisect_left, insort class SqrtCountLess: def __init__(self, a): self.a = list(a) self.b = max(1, math.isqrt(len(self.a))) self.blocks = [sorted(self.a[k:k + self.b]) for k in range(0, len(self.a), self.b)] def update(self, i, value): blk = self.blocks[i // self.b] blk.pop(bisect_left(blk, self.a[i])) # убрали старое значение insort(blk, value) # вставили новое self.a[i] = value def count_less(self, l, r, x): # сколько a[i] < x на [l..r] b = self.b bl, br = l // b, r // b if bl == br: return sum(1 for i in range(l, r + 1) if self.a[i] < x) res = sum(1 for i in range(l, (bl + 1) * b) if self.a[i] < x) res += sum(1 for i in range(br * b, r + 1) if self.a[i] < x) for k in range(bl + 1, br): res += bisect_left(self.blocks[k], x) return res
Обновление — (вставка в список длины B), запрос — . Здесь уже выгодно взять блок чуть больше , примерно , чтобы уравновесить хвосты и бинпоиски по блокам.
Ещё задачи, где блоки удобнее:
- разворот или циклический сдвиг подотрезка, вставка и удаление элементов в середине — блоки хранят как список списков и периодически перестраивают;
- «присвоить на отрезке» вместе с «прибавить на отрезке» — две метки на блок вместо аккуратной композиции ленивых операций в дереве;
- запросы, где ответ для блока — целая структура (словарь частот, отсортированный массив, битсет).
Корень, дерево отрезков или Фенвик
| Корневая декомпозиция | Дерево отрезков | Дерево Фенвика | |
|---|---|---|---|
| Запрос | |||
| Точечное обновление | O(1) – | ||
| Операции на отрезке | метка на блок | ленивые метки | только частные случаи |
| Операции | любые, что считаются по блоку | ассоциативные | обратимые: сумма, XOR |
| Минимум с обновлениями | да | да | неудобно |
| Объём кода | ~30 строк | ~50–80 строк | ~15 строк |
| Нестандартные запросы | легко | бывает сложно | почти никогда |
Ориентироваться можно так:
- Сумма с точечными обновлениями — дерево Фенвика. Короче и быстрее всего.
- Минимум, максимум, ленивые операции, жёсткие ограничения — дерево отрезков. против : разница в константе ощутимая.
- Нестандартный запрос или мало времени на написание — корневая декомпозиция. Особенно если укладывается в лимит: для это около операций — нормально для C++ и Java, но на чистом Python может не пройти по времени.
Про оценку сложности на собеседовании подробнее — в статье про O-нотацию.
Алгоритм Мо: корень по запросам
Идея блоков работает не только для массива, но и для запросов. Если все запросы известны заранее и обновлений нет, можно отсортировать их так, чтобы ответ для следующего отрезка получался из предыдущего небольшим сдвигом границ. Запросы группируют по блоку левой границы (l // B), внутри группы — по правой границе. Тогда суммарное перемещение указателей — .
Так решают, например, «число различных элементов на отрезке»: при сдвиге границы на один элемент обновляем словарь частот за O(1). Подробный разбор, порядок сортировки и типичные ловушки — в отдельной статье про алгоритм Мо.
Частые ошибки
- Не обработан случай «
lиrв одном блоке». Отрезок считается дважды или с пропусками. Эту ветку пишут первой. - Неполный последний блок. Если
nне делится наB, у последнего блока меньше элементов. Срезы в Python сами обрезаются по длине массива, но при умножении метки на длину блока нужно брать реальную длину. - Путаница с границами. Решите заранее,
rвключительно или нет, и придерживайтесь этого. В коде выше — включительно, отсюдаr + 1в срезах. - Минимум «по дельте». Для суммы
sums[k] += value - a[i]корректно, для минимума — нет: блок нужно пересчитать. - Забытая метка в неполном блоке. При запросе на хвосте блока с ненулевым
add[k]метку нужно учесть для каждого элемента хвоста. B = 0на пустом или единичном массиве. Отсюдаmax(1, ...)при выборе размера блока.- Слепая вера в √n. Если обновления и запросы стоят по-разному (как в примере с бинпоиском), оптимальный
Bдругой. На практике его иногда подбирают замером.
Где встречается на собеседованиях
На классических интервью в продуктовые компании корневую декомпозицию спрашивают редко: задачу «сумма на отрезке с обновлениями» (LeetCode 307, Range Sum Query — Mutable) обычно ждут решения деревом Фенвика или деревом отрезков. Но корень — честное решение с понятной оценкой, и его вполне можно предложить, если вы забыли, как пишется дерево. Хорошо, если вы сами назовёте компромисс: « на операцию, при это около 170 операций на запрос, пройдёт».
В олимпиадном программировании корень встречается гораздо чаще: блоки, алгоритм Мо, деление запросов на «тяжёлые» и «лёгкие» по порогу .
Что запомнить
- Массив режется на блоки по , для каждого блока хранится готовый ответ.
- Запрос = хвост блока + целые блоки + начало блока, всё вместе за .
- Сумма обновляется за O(1) через дельту, минимум — пересчётом блока.
- Операции на отрезке — метка на блок, это двухуровневая версия ленивого дерева отрезков.
- По скорости корень проигрывает дереву отрезков и Фенвику, но выигрывает простотой и гибкостью.