Тапсырмалар № 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}$.

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

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

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

Главное