Как организовать обработку одномерного и двумерного массива?

Массив хранит элементы одного типа и предоставляет доступ по индексу. Его сила — быстрый переход к известной позиции, а ограничение — необходимость аккуратно управлять границами…

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

Диапазон индексов

При длине n допустимы позиции от 0 до n − 1 в языках с нулевой индексацией. Условие цикла i < n прямо выражает эту границу. Обращение к i + 1 требует более строгой верхней границы, например i + 1 < n, иначе последняя итерация выйдет за массив.

Префиксные суммы

Массив prefix строят так, чтобы prefix[k] хранил сумму первых k элементов. Тогда сумма полуинтервала [l, r) равна prefix[r] − prefix[l]. Нулевая начальная ячейка делает формулу одинаковой для отрезка от начала и исключает специальную ветку.

Двумерный обход

В матрице внешний цикл обычно выбирает строку, внутренний — столбец. Для главной диагонали нужны элементы a[i][i], для побочной — a[i][n − 1 − i] квадратной матрицы. Прямоугольную таблицу нельзя молча считать квадратной: число строк и столбцов проверяют отдельно.

Изменение на месте

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

Набор границ

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

Префикс превращает запрос в вычитание

Пусть prefix[i] равен сумме первых i элементов, причём prefix[0] = 0. Тогда сумма полуинтервала [left, right) равна prefix[right] − prefix[left]. Нулевая ячейка убирает отдельное ветвление для диапазона, начинающегося с первого элемента.

def prefix_sums(values: list[int]) -> list[int]:
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix: list[int], left: int, right: int) -> int:
    return prefix[right] - prefix[left]

data = [4, -1, 7, 2]
prefix = prefix_sums(data)
assert range_sum(prefix, 1, 4) == 8

Построение занимает O(n), каждый запрос — O(1), память — O(n). Для одного запроса обычный проход проще; выигрыш появляется при множестве запросов к неизменяемому массиву.

Практика: суммы прямоугольников

Обобщите идею на матрицу: prefix[i][j] хранит сумму прямоугольника от начала до позиции, не включая i и j. Выведите формулу включений и исключений для произвольного прямоугольника и реализуйте её. Проверьте матрицу 1×1, одну строку, весь массив и внутренний прямоугольник. Затем объясните, почему изменение одного исходного элемента делает прежний префикс недействительным и какая задача потребует другой структуры данных.