Корневая декомпозиция
Рассмотрим следующую учебную задачу: Дан массив $a_1,\ a_2,\ \ldots,\ a_n$. Надо обрабатывать два типа запросов:
- Найти сумму на отрезке $[l;\ r]$.
- Увеличить значение элемента $a_pos\ +=\ x$
Решение
Разобьем массив на блоки размера $K = O(\sqrt n)$. Кроме обычной последовательности, будем хранить сумму чисел в блоке. При запросе обновления можно за $O(1)$ обновить элемент последовательности и пересчитать соответствующий блок. Для get-запроса просмотрим все блоки, которые находятся внутри отрезка запроса, и прибавим к ответу посчитанную сумму. А также отдельно рассмотрим все элементы, которые не попали ни в один блок. Количество нужных нам блоков — это $O(\frac{n}{k}) = O(\sqrt n)$, число единичных элементов также $O(k) = O(\sqrt n)$.
1 int a[MAXN];
2 int b[MAXN];
3 int k = 400; // предпочтительно писать константу
4
5 void build() {
6 for (int i = 0; i < n; i++) {
7 b[i / k] += a[i];
8 }
9 }
10
11 int sum(int l, int r) {
12 int res = 0;
13 while (l <= r) {
14 if (l % k == 0 && l + k - 1 <= r) {
15 res += b[l / k];
16 l += k;
17 }
18 else {
19 res += a[l];
20 l += 1;
21 }
22 }
23 return res;
24 }
25
26 void upd(int pos, int x) {
27 a[pos] += x;
28 b[pos / k] += x;
29 }
Изменение на отрезке
В корневой можно пользоваться техникой отложенных операций. Это выглядит вот так: мы запомним $push$-величину, которую будем проталкивать перед обращению к $\textit{одиночным}$ элементам $a_i$
1 void push(int block) {
2 if (add[block] == 0) {
3 return;
4 }
5 for (int i = block * k; i < min(n, (block + 1) * k); i++) {
6 a[i] += add[block];
7 }
8 add[block] = 0;
9 }
10
11 void upd(int l, int r, int x) {
12 while (l <= r) {
13 if (l % c == 0 && l + k - 1 <= r) {
14 b[l / k] += k * x;
15 add[l / k] += x;
16 l += k;
17 }
18 else {
19 a[l] += x;
20 l++;
21 }
22 }
23 }
Отсортированные последовательности
В блоках корневой можно хранить не только значения функций для подотрезка, а еще и его отсортированную версию. Это бывает полезно при ответе на запросы вида "число меньших $x$ на отрезке" и используется в техниках split-rebuild и split-merge.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s