SQRT-декомпозиция

Дана следующая задача: есть массив чисел $a$ длины $n$ и $m$ запросов двух видов:

1. $Q \ l \ r$ - узнать сумму на отрезке $[l, r]$
2. $A \ i \ x$ - прибавить к элементу $i$ значение $x$

Идея

Разобьём массив на блоки размера примерно по $\sqrt(n)$. Для каждого блока посчитаем сумму элементов в нём.

Теперь при запросе первого типа можно разбить запрос на несколько частей: одна часть - блоки, вошедшие в запрос целиком, вторая - “хвосты” слева и справа. Блоков будет не более $\sqrt(n)$ и для них ответ считается за $O(1)$, а в хвостах суммарно не более $2\sqrt(n)$ элементов. Итого ответ на запрос за $O(\sqrt(n))$ и итоговая асимптотика - $O(n + m\sqrt(n))$.

Обобщение

Решение тривиально модифицируется до случая с массовыми операциями: для каждого блока будем дополнительно хранить, сколько необходимо дополнительно прибавить ко всем числам в этом блоке. При прибавлении ко блоку будем модифицировать это значение, а при прибавлении к отдельному числу - изменять его явно.

Примечания

Зачастую размер блоков задают равным некоторой константе, являющейся примерно $\sqrt(n)$ при $n = max$. Если задача получает TL - бывает полезно попробовать немного поменять значение этой константы в ту или иную сторону.

Реализация (вместо запроса прибавления - запрос изменения значения на $x$)

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll n, k;

int main() {
    ll q;
    cin >> n >> q;
    ll max_n = 1000000;
    k = 400;
    vector <ll> a(max_n), b(max_n / k);
    while (q--) {
        char c;
        cin >> c;
        if (c == 'Q') {
            ll l, r, ans = 0;
            cin >> l >> r;
            l--; r--;
            while (l <= r) {
                if (l % k == 0 && l + k - 1 <= r) {
                    ans += b[l / k];
                    l += k;
                } else {
                    ans += a[l];
                    ++l;
                }
            }
            cout << ans << endl;
        } else if (c == 'A') {
            ll w, x;
            cin >> w >> x;
            w--;
            b[w / k] = b[w / k] - a[w] + x;
            a[w] = x;
        }
    }
}