Корневая декомпозиция на массиве

Материал из Algocode wiki
Версия от 17:06, 5 декабря 2020; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Рассмотрим следующую учебную задачу: Дан массив $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 % k == 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