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