​​Разностные массивы

Давно не было постов, и пока восьмибитный котик продолжает корпеть над очередной статьей по V8, моргая раз в пять минут и делая вид, что он все понимает в исходниках. Сегодня освежу блог чем-то чуть более интересным и полезным.

Последние пару лет я старался начать утро с "разгона" на дейликах, но не тех, что вам ставят в календарь на 10 утра, а с задачами на LeetCode. Несколько раз даже попытался порешать контесты, но необходимость просыпаться в воскресенье в 5 утра, чтобы успеть к началу, быстро развеяли надежды на высокий рейтинг (да-да, еще есть biweekly, но сейчас не об этом).

Ладно, хватит лирики.

Вчера (пока писал -- уже позавчера позавчера) на daily попалась любопытная задача, которая использует префиксные суммы не для подсчета сумм на отрезках, а для применения большого числа операций за один проход.

Increment Submatrices by One

Дана матрица n × n, заполненная нулями, и список запросов формата [row1, col1, row2, col2]. Каждый такой запрос увеличивает на 1 значения во всех ячейках подматрицы от (row1, col1) до (row2, col2) включительно. Нужно вернуть итоговую матрицу после применения всех запросов.

Добавим визуальный пример

Начальная матрица 3x3 и запросы [0,0,1,1] и [1,1,2,2]

[0 0 0]
[0 0 0]
[0 0 0]

После первого запроса [0,0 → 1,1]:

[1 1 0]
[1 1 0]
[0 0 0]

После второго запроса [1,1 → 2,2]:

[1 1 0]
[1 2 1]
[0 1 1]

Решение в лоб (brute-force)

Создаем матрицу нужного размера и заполняем ее нулями. Создаем цикл из запросов на увеличение каждой клетки. И создаем цикл обхода по строкам и по колонкам.

Код примерно такой:

for (const [row1, col1, row2, col2] of queries) {
  for (let row = row1; row <= row2; row++) {
    for (let col = col1; col <= col2; col++) {
      matrix[row][col] += 1;
    }
  }
}

Итого в худшем случае мы можем получить O(q * n * n)

Отложенная симуляция

Для упрощения вложенности нам не следует обновлять каждую позицию, вместо этого мы можем поставить операции для старта и финиша. Для примера рассмотрим не всю матрицу, а только первую строку.
У нас есть запрос, который должен увеличить на 1 колонки с индексом 0 и 1. Значит старт у нас в нулевом индексе, и в это колонку мы записываем +1. Теперь нам нужно найти финиш, т.е. установить в колонке обратную операцию, у нас это -1. Так как первый запрос изменял только нулевой и первый столбец, то финиш у нас на 2 столбце. Столбец с индексом 1 никак не изменяется.

Исходный массив

[0 0 0 0]

Применяем запрос на увеличение [0, 1] для упрощения только col1 и сol2.

[+1 0 -1 0]

Берем второй запрос на увеличение [1, 2]

// исходная строка
[+1 0 -1 0]
// изменения
[ . +1 0 -1]
// результат
[+1 +1 -1 -1]

А теперь один раз пробегаем префиксной суммой по результату и полностью восстанавливаем массив с учетом всех операций

// массив операций
[+1 +1 -1 -1]
// восстановленный массив
[1 2 1 0]

Теперь остается лишь применить это для всей матрицы проходя по каждой из ее строк.

Сложность решения будет:
1. обработка всех запросов. Худший случай O(query * row)
2. восстановление всей матрицы O(rol * col)

Итого получается O(q * r + r * c)

Почему это работает

Мы устанавливаем границу влияния со стартом и финишем, то при проходе префиксом значение проставляется всем элементам от старта до финиша.

Применени в реальных задачах

Паттерн разностных массивов полезен, когда нужно запомнить события на временной шкале, так как не нужно постоянно хранить текущее значение. Его всегда можно восстановить, проведя симуляцию.

---
#JavaScript #LeetCode #PrefixSum #DifferenceArrays #Algorithm #8BitJS