|
|
| (не показана 1 промежуточная версия 1 участника) |
| Строка 1: |
Строка 1: |
| − | Рассмотрим следующую учебную задачу: Дан массив $a_1,\ a_2,\ \ldots,\ a_n$. Надо обрабатывать два типа запросов:
| + | Иногда в задаче возникают ситуации, когда мы умеем решать ее когда какое-то свойство < $\sqrt{N}$ и больше $\sqrt{N}$. Данный подход и называется корневой декомпозицией(оптимизацией). |
| − | * Найти сумму на отрезке $[l;\ r]$.
| |
| − | * Увеличить значение элемента $a_pos\ +=\ x$
| |
| | | | |
| − | ===Решение===
| + | Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A B \le N$, то одно из чисел < $\sqrt{N}$. |
| − | Разобьем массив на блоки размера $K = O(\sqrt n)$. Кроме обычной последовательности, будем хранить сумму чисел в блоке. При запросе обновления можно за $O(1)$ обновить элемент последовательности и пересчитать соответствующий блок. Для get-запроса просмотрим все блоки, которые находятся внутри отрезка запроса, и прибавим к ответу посчитанную сумму. А также отдельно рассмотрим все элементы, которые не попали ни в один блок. Количество нужных нам блоков — это $O(\frac{n}{k}) = O(\sqrt n)$, число единичных элементов также $O(k) = O(\sqrt n)$.
| |
| | | | |
| − | <syntaxhighlight lang='c++' line='line'>
| + | {{Автор|Глеб Лобанов|glebodin}} |
| − | int a[MAXN];
| |
| − | int b[MAXN];
| |
| − | int k = 400; // предпочтительно писать константу
| |
| − | | |
| − | void build() {
| |
| − | for (int i = 0; i < n; i++) {
| |
| − | b[i / k] += a[i];
| |
| − | }
| |
| − | }
| |
| − | | |
| − | int sum(int l, int r) {
| |
| − | int res = 0;
| |
| − | while (l <= r) {
| |
| − | if (l % k == 0 && l + k - 1 <= r) {
| |
| − | res += b[l / k];
| |
| − | l += k;
| |
| − | }
| |
| − | else {
| |
| − | res += a[l];
| |
| − | l += 1;
| |
| − | }
| |
| − | }
| |
| − | return res;
| |
| − | }
| |
| − | | |
| − | void upd(int pos, int x) {
| |
| − | a[pos] += x;
| |
| − | b[pos / k] += x;
| |
| − | }
| |
| − | </syntaxhighlight>
| |
| − | | |
| − | ====Изменение на отрезке====
| |
| − | | |
| − | В корневой можно пользоваться техникой [[отложенные операции|отложенных операций]]. Это выглядит вот так: мы запомним $push$-величину, которую будем проталкивать перед обращению к $\textit{одиночным}$ элементам $a_i$
| |
| − | <syntaxhighlight lang='c++'line='line'>
| |
| − | void push(int block) {
| |
| − | if (add[block] == 0) {
| |
| − | return;
| |
| − | }
| |
| − | for (int i = block * k; i < min(n, (block + 1) * k); i++) {
| |
| − | a[i] += add[block];
| |
| − | }
| |
| − | add[block] = 0;
| |
| − | }
| |
| − | | |
| − | void upd(int l, int r, int x) {
| |
| − | while (l <= r) {
| |
| − | if (l % c == 0 && l + k - 1 <= r) {
| |
| − | b[l / k] += k * x;
| |
| − | add[l / k] += x;
| |
| − | l += k;
| |
| − | }
| |
| − | else {
| |
| − | a[l] += x;
| |
| − | l++;
| |
| − | }
| |
| − | }
| |
| − | }
| |
| − | </syntaxhighlight>
| |
| − | | |
| − | ====Отсортированные последовательности====
| |
| − | | |
| − | В блоках корневой можно хранить не только значения функций для подотрезка, а еще и его отсортированную версию. Это бывает полезно при ответе на запросы вида "число меньших $x$ на отрезке" и используется в техниках [[split-rebuild]] и [[split-merge]].
| |
| − | | |
| − | {{Автор|Константин Амеличев|kik0s}} | |
| | [[Категория:Конспект]] | | [[Категория:Конспект]] |
| − | [[Категория:Структуры данных для запросов на отрезках]]
| |
Иногда в задаче возникают ситуации, когда мы умеем решать ее когда какое-то свойство < $\sqrt{N}$ и больше $\sqrt{N}$. Данный подход и называется корневой декомпозицией(оптимизацией).
Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A B \le N$, то одно из чисел < $\sqrt{N}$.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin