Корневая декомпозиция (sqrt decomposition): как отвечать на запросы суммы на отрезке за O(sqrt n)?

Идея: разбиваем массив на блоки длины примерно B = sqrt(n). Для каждого блока заранее храним его сумму. Тогда:

• Точечное обновление a[i] += d: меняем a[i] и сумму его блока — O(1).
• Запрос суммы [l, r]: края обрабатываем поэлементно (не больше двух неполных блоков, каждый длины < B → O(B)), а целые блоки между ними берём уже посчитанными суммами (их не больше n/B штук → O(n/B)). Итого O(B + n/B), минимум при B = sqrt(n) → O(sqrt n) на запрос.

int n, B;
vector<long long> a, blockSum;

void build() {
    B = max(1, (int)sqrt((double)n));
    blockSum.assign((n + B - 1) / B, 0);
    for (int i = 0; i < n; i++) blockSum[i / B] += a[i];
}
void update(int i, long long val) {
    blockSum[i / B] += val - a[i];
    a[i] = val;
}
long long query(int l, int r) {            // включительно
    long long res = 0;
    int bl = l / B, br = r / B;
    if (bl == br) {                         // один блок целиком в крае
        for (int i = l; i <= r; i++) res += a[i];
    } else {
        for (int i = l; i < (bl + 1) * B; i++) res += a[i];     // левый край
        for (int b = bl + 1; b < br; b++) res += blockSum[b];   // целые блоки
        for (int i = br * B; i <= r; i++) res += a[i];          // правый край
    }
    return res;
}

Построение O(n), запрос/обновление O(sqrt n), память O(n). Выбор B = sqrt(n) — это минимум суммы B + n/B по AM-GM. Корневая проще дерева отрезков в реализации и легко обобщается на «отложенные» обновления на блок (пометки на блок + ленивое пересчитывание края).