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

Рассмотрим следующую задачу: дан массив $a_1,\ \dots,\ a_n$. Надо обрабатывать два типа запросов:

• $+= x$ на отрезке $[l, r]$
• $? a_i$

Хотим решение за $O((n + q) \cdot \sqrt{q})$ Давайте мы будем запоминать все $update-$запросы, которые к нам пришли, в буфер $buf$. Тогда ответ на $get-$запрос потребует от нас $|buf|$ опреаций. Давайте раз в $O(\sqrt{q})$ операций будем очищать буфер и применять все запросы к массиву сразу (с помощью сканлайна).

 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