Корневая по запросам

Давайте теперь разбивать на сам массив, а запросы к нему. Например, у нас есть такая структура, как префиксные суммы, которая позволяет находить сумму на отрезке за $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