Корневая по запросам: различия между версиями

Текущая версия на 15:55, 22 октября 2019

Давайте теперь разбивать на сам массив, а запросы к нему. Например, у нас есть такая структура, как префиксные суммы, которая позволяет находить сумму на отрезке за $O(1)$ без запросов обновления, мы можем честно пересчитывать ее каждый $\sqrt{M}$ запросов.

Теперь поговорим о самих запросах:

Так как мы пересчитываем префиксные суммы каждые $\sqrt{M}$ запросов, то мы не рассмотрели все запросы, лежащие после предыдущего обновления, таких запросов не может быть больше $\sqrt{M}$, то есть мы можем явно хранить список еще не обработанных запросов.

Тогда если мы встречаем запрос обновления, то просто добавим его в список, требующий обновления.

В случае запроса суммы просто возьмем ответ с помощью префиксных сумм и прибавим ответы на запросы.

 1 for (int i = 0; i < q; i++) {
 2     if (i % K == 0) {
 3          rebuild();
 4     }
 5     query q;
 6     cin >> q;
 7     if (q.type == "update") {
 8         buffer.push_back(q);
 9     }
10     else {
11         int ans = a[q.pos];
12         for (auto x : buffer) {
13             if (q.l <= x.pos && x.pos <= q.r) {
14                ans += x.add;
15             } 
16         }
17         cout << ans << '\n';
18     }
19 }

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin

@@ Строка 1: / Строка 1: @@
-Рассмотрим следующую задачу: дан массив $a_1,\ \dots,\ a_n$. Надо обрабатывать два типа запросов:
+Давайте теперь разбивать на сам массив, а запросы к нему. Например, у нас есть такая структура, как префиксные суммы, которая позволяет находить сумму на отрезке за $O(1)$ без запросов обновления, мы можем честно пересчитывать ее каждый $\sqrt{M}$ запросов.
-* $+= x$ на отрезке $[l, r]$
-* $? a_i$
-Хотим решение за $O((n + q) \cdot \sqrt{q})$
+Теперь поговорим о самих запросах:
-Давайте мы будем запоминать все $update-$запросы, которые к нам пришли, в буфер $buf$. Тогда ответ на $get-$запрос потребует от нас $|buf|$ опреаций. Давайте раз в $O(\sqrt{q})$ операций будем очищать буфер и применять все запросы к массиву сразу (с помощью сканлайна).
+Так как мы пересчитываем префиксные суммы каждые $\sqrt{M}$ запросов, то мы не рассмотрели все запросы, лежащие после предыдущего обновления, таких запросов не может быть больше $\sqrt{M}$, то есть мы можем явно хранить список еще не обработанных запросов.
+Тогда если мы встречаем запрос обновления, то просто добавим его в список, требующий обновления.
+В случае запроса суммы просто возьмем ответ с помощью префиксных сумм и прибавим ответы на запросы.
 <syntaxhighlight lang='c++' line='line>
@@ Строка 29: / Строка 32: @@
 {{Автор|Константин Амеличев|kik0s}}
+{{Автор|Глеб Лобанов|glebodin}}
 [[Категория:Конспекты]]
 [[Категория:Корневая]]