🔢 Едномерни Масиви: Основи и Задачи

Масивът (Array) е най-простата структура от данни, която съхранява поредица от елементи от един и същи тип на последователни адреси в паметта.

1. Декларация и Достъп

1.1. Статични масиви

Размерът трябва да е известен по време на компилация (освен при VLA в C99, но в C++ не се препоръчва).

int arr[100]; // Масив от 100 цели числа
arr[0] = 5;   // Индексацията започва от 0!

1.2. Глобални vs Локални масиви

Локални (във функция): Заделят се в Стека (Stack). Паметта е ограничена (обикновено няколко MB). Ако дефинирате int a[1000000] вътре в main, ще получите "Stack Overflow".
Глобални (извън функции): Заделят се в Static/Data segment. Може да са много големи (до стотици MB). Освен това автоматично се инициализират с нули.

int bigArr[1000005]; // OK, глобален

int main() {
    // int huge[1000005]; // ГРЕШКА! Препълване на стека.
}

2. Често срещани грешки

2.1. Излизане от граници (Out of Bounds)

C++ не прави проверка дали индексът е валиден.

int a[5];
a[5] = 10; // ГРЕШКА! Валидни са 0, 1, 2, 3, 4.

Това може да доведе до промяна на други променливи, безкрайни цикли или "Segmentation Fault".

2.2. Off-by-one errors

Объркване дали цикълът трябва да е < N или <= N. При 0-базирани масиви винаги е < N.

3. Основни алгоритми

3.1. Намиране на минимум и максимум

int minVal = arr[0];
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] < minVal) minVal = arr[i];
    if (arr[i] > maxVal) maxVal = arr[i];
}
// Или std::min_element / std::max_element

3.2. Сума и Средно аритметично

long long sum = 0; // Ползвайте long long, за да избегнете overflow
for (int i = 0; i < n; i++) sum += arr[i];
double avg = (double)sum / n;

3.3. Обръщане (Reverse)

Разменяме първия с последния, втория с предпоследния и т.н.

for (int i = 0; i < n / 2; i++) {
    swap(arr[i], arr[n - 1 - i]);
}

3.4. Проверка за сортираност

bool isSorted = true;
for (int i = 0; i < n - 1; i++) {
    if (arr[i] > arr[i+1]) {
        isSorted = false;
        break;
    }
}

4. `std::vector` - Модерният масив

В C++ почти винаги е по-добре да ползвате std::vector. * Динамичен размер. * Пази си размера (v.size()). * Съхранява се в Heap (Купчината), така че може да е голям дори ако е локален.

vector<int> v(n); // Вектор с n елемента (нули)
v.push_back(5);   // Добавяне накрая

5. Техника на двата указателя (Two Pointers)

Често срещана техника за решаване на задачи с масиви за линейно време.

5.1. Премахване на дубликати от сортиран масив

int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int writePos = 1;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] != arr[i-1]) {
            arr[writePos++] = arr[i];
        }
    }
    return writePos;
}

5.2. Намиране на двойка с дадена сума (в сортиран масив)

Сложност: \(O(N)\) вместо \(O(N^2)\).

bool findPairWithSum(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }
    return false;
}

6. Префиксни суми (Prefix Sums)

Позволяват бързо пресмятане на сумата на елементите в интервал \([L, R]\).

6.1. Основна идея

Създаваме масив prefix, където prefix[i] съдържа сумата на елементите от 0 до i-1.

vector<long long> buildPrefix(const vector<int>& arr) {
    int n = arr.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

6.2. Запитвания за сума в интервал

След като сме построили префиксния масив, всяко запитване се отговаря за \(O(1)\).

// Сума на елементите от индекс L до R (включително)
long long rangeSum(const vector<long long>& prefix, int L, int R) {
    return prefix[R + 1] - prefix[L];
}

6.3. Приложение: Най-много K нули в подмасив

Задача: Намерете най-дългия подмасив от 0 и 1, който съдържа най-много K нули.

int longestSubarrayWithKZeros(vector<int>& arr, int K) {
    int left = 0, zeros = 0, maxLen = 0;
    for (int right = 0; right < arr.size(); right++) {
        if (arr[right] == 0) zeros++;
        while (zeros > K) {
            if (arr[left] == 0) zeros--;
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

7. Разностен масив (Difference Array)

Позволява бързо обновяване на интервали.

7.1. Идея

Ако искаме да добавим x към всички елементи в интервал [L, R], използваме разностен масив.

vector<int> diff(n + 1, 0);
// Добавяне на x към интервал [L, R]
diff[L] += x;
diff[R + 1] -= x;
// Възстановяване на оригиналния масив
for (int i = 1; i < n; i++) {
    diff[i] += diff[i - 1];
}

Това позволява \(O(1)\) обновяване на интервал и \(O(N)\) възстановяване.

8. Циклично ротиране на масив

Отместване на елементите наляво или надясно с K позиции.

8.1. Ротиране надясно

void rotateRight(vector<int>& arr, int K) {
    int n = arr.size();
    K %= n; // Ако K > n
    reverse(arr.begin(), arr.end());
    reverse(arr.begin(), arr.begin() + K);
    reverse(arr.begin() + K, arr.end());
}

8.2. Ротиране наляво

void rotateLeft(vector<int>& arr, int K) {
    rotateRight(arr, arr.size() - K);
}

9. Kadane's Algorithm - Максимална сума на подмасив

Класическа задача: Намерете подмасив с максимална сума.

long long maxSubarraySum(const vector<int>& arr) {
    long long maxSum = arr[0], currentSum = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        currentSum = max((long long)arr[i], currentSum + arr[i]);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

10. Честотни масиви (Frequency Arrays)

Използват се за бързо броене на срещанията на елементи.

10.1. Пример

const int MAXVAL = 1000005;
int freq[MAXVAL];
memset(freq, 0, sizeof(freq));

// Броене
for (int i = 0; i < n; i++) {
    freq[arr[i]]++;
}

// Намиране на най-честия елемент
int maxFreq = 0, mostFrequent = arr[0];
for (int i = 0; i < MAXVAL; i++) {
    if (freq[i] > maxFreq) {
        maxFreq = freq[i];
        mostFrequent = i;
    }
}

11. Задачи за упражнение

Обръщане на масив: Четене на масив и извеждане в обратен ред.
Втори по величина: Намиране на втория най-голям елемент за \(O(N)\).
Премахване на дубликати: От сортиран масив, използвайки техниката на двата указателя.
Циклично ротиране: Отместване на масив наляво/надясно с K позиции.
Префиксни суми: Задача с много запитвания за сума в интервал.
Двойка с най-близка сума: В сортиран масив, намерете двойка числа с най-близка сума до дадено число.
Kadane: Намерете максималната сума на подмасив.
Най-дълъг подмасив: С най-много K различни числа.

🏁 Заключение

Масивите са основата на програмирането и алгоритмите. Уверете се, че разбирате напълно индексацията (започва от 0!), границите на масива и основните техники като префиксни суми, два указателя и Kadane's algorithm. Грешките "плюс/минус единица" (off-by-one errors) са най-честата причина за грешни решения в състезанията. Практикувайте с множество задачи, за да развиете интуиция и скорост при работа с масиви.