ЕГЭОГЭ
РУҚА
Задания № 12, 17 · ЕГЭ

Подмассив

Непрерывная часть массива с заданными границами
2 мин чтенияСложность: Обновлено 29 сентября 2026

Подмассив — это часть массива, состоящая из элементов, расположенных подряд. Чтобы задать подмассив, достаточно указать индекс первого и индекс последнего элемента.

ПодмассивСлово образовано от «массив» с приставкой «под-» и означает часть массива.
Подмассивом массива \(A\) называется последовательность элементов \(A[l], A[l+1], \ldots, A[r]\), где \(l\) и \(r\) — границы подмассива, причём \(l \le r\). В подмассиве сохраняется исходный порядок элементов, а пропускать элементы между \(l\) и \(r\) нельзя.

Границы и длина

Обычно границы подмассива включительные: элементы с индексами \(l\) и \(r\) входят в него. Если массив индексируется с нуля, то подмассив \(A[l..r]\) содержит элементы от \(A[l]\) до $A[r]]. Его длина равна разности правой и левой границ, увеличенной на единицу.

\[\operatorname{len}(A[l..r]) = r-l+1\]

Например, при \(l=2\) и \(r=5\) в подмассив входят четыре элемента: с индексами \(2,3,4,5\). При индексах с единицы правило остаётся тем же.

№
Пример

Пусть \(A=[4,7,1,9,3,8]\). Подмассив \(A[1..4]\) при нумерации с нуля равен \([7,1,9,3]\). Его границы: \(l=1\), \(r=4\), длина: \(4-1+1=4\).

Как перебрать подмассивы

Чтобы обработать один подмассив, фиксируют его границы и перебирают индексы \(i\) от \(l\) до \(r\) включительно. Чтобы перебрать все подмассивы, выбирают левую границу \(l\), затем правую границу \(r\) от \(l\) до последнего индекса массива. Для ускорения обработки границ иногда применяют метод двух указателей, а для вычислений на отрезках — обработку отрезка массива.

Псевдокод
для l от 0 до n - 1
    для r от l до n - 1
        обработать A[l..r]

Количество всех непустых подмассивов массива длины \(n\) равно числу пар границ \(l,r\), для которых \(0 \le l \le r < n\).

\[\frac{n(n+1)}{2}\]
!
Не перепутайте

Подмассив — непрерывный фрагмент. Элементы с индексами \(1,3,5\) не образуют подмассив, потому что между ними пропущены элементы. Такая выборка является подпоследовательностью, но не подмассивом.

Проверьте себя

Сколько элементов содержит подмассив \(A[3..7]\)?

Главное за минуту

Главное

  • Подмассив — непрерывная часть массива, задаваемая границами \(l\) и \(r\).
  • При включительных границах длина равна \(r-l+1\).
  • Все непустые подмассивы массива длины \(n\) можно перебрать двумя вложенными циклами; их количество равно \(\frac{n(n+1)}{2}\).