Массив разностей

O(n)

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

Сигналы

сначала много обновлений диапазонов, затем один раз прочитать итоговый массивприбавить значение к каждому элементу диапазона, повторить много разприменить k приращений диапазона перед тем как отвечать на запросысчётчики бронирований/интервалов по массиву

Шаблон

function applyRangeUpdates(n, updates) {
    const diff = new Array(n + 1).fill(0);
    for (const [l, r, val] of updates) {
        diff[l] += val;
        diff[r + 1] -= val;
    }
    const result = new Array(n);
    let running = 0;
    for (let i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}

Похоже, но не то

Префиксные суммы: Префиксные суммы нужны для многих запросов ЧТЕНИЯ диапазона в фиксированном массиве. Массив разностей нужен для обратного порядка работы: сначала много ОБНОВЛЕНИЙ диапазонов, а сам массив материализуется только один раз в конце.

n до 1e5..1e6 при q обновлениях диапазонов -> O(n + q): каждое обновление это две точечные правки за O(1), а один финальный проход префиксных сумм за O(n) восстанавливает массив, вместо O(n) на каждое обновление.

Изучить этот паттерн