Arreglos y Vectores

Introducción

Los arreglos y vectores son las estructuras de datos más básicas y utilizadas. Entenderlos bien es fundamental para resolver cualquier problema.

Arrays estáticos vs Vectores

Arrays estáticos (C-style)

// Declaración
int arr[100];           // Sin inicializar
int arr[100] = {};      // Inicializado a 0
int arr[] = {1, 2, 3};  // Tamaño automático

// Acceso
arr[0] = 10;            // Primer elemento
arr[99] = 20;           // Último elemento

Vectores (STL)

#include <vector>

// Declaración
vector<int> v;                    // Vector vacío
vector<int> v(100);               // 100 elementos (valor por defecto)
vector<int> v(100, -1);           // 100 elementos inicializados a -1
vector<int> v = {1, 2, 3, 4, 5};  // Lista de inicialización

// Tamaño
int n = v.size();
bool vacio = v.empty();

Operaciones básicas con vectores

Agregar y eliminar elementos

vector<int> v = {1, 2, 3};

// Agregar al final - O(1) amortizado
v.push_back(4);     // v = {1, 2, 3, 4}

// Eliminar del final - O(1)
v.pop_back();       // v = {1, 2, 3}

// Insertar en posición específica - O(n)
v.insert(v.begin() + 1, 10);  // v = {1, 10, 2, 3}

// Eliminar de posición específica - O(n)
v.erase(v.begin() + 1);       // v = {1, 2, 3}

// Limpiar todo
v.clear();          // v = {}

Acceso a elementos

vector<int> v = {10, 20, 30, 40, 50};

// Por índice
int a = v[0];       // 10 (sin verificación de límites)
int b = v.at(0);    // 10 (con verificación, lanza excepción si fuera)

// Primero y último
int primero = v.front();  // 10
int ultimo = v.back();    // 50

Redimensionar

vector<int> v = {1, 2, 3};

v.resize(5);        // v = {1, 2, 3, 0, 0}
v.resize(5, -1);    // v = {1, 2, 3, -1, -1}
v.resize(2);        // v = {1, 2}

Iteradores

Los iteradores permiten recorrer y manipular contenedores:

vector<int> v = {10, 20, 30};

// Recorrer con iteradores
for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}

// Range-based for (más limpio)
for (int x : v) {
    cout << x << " ";
}

// Con referencia para modificar
for (int& x : v) {
    x *= 2;  // Duplica cada elemento
}

Vectores 2D (matrices)

Declaración

// Matriz de tamaño fijo
vector<vector<int>> matriz(n, vector<int>(m, 0));
// n filas, m columnas, inicializado a 0

// Matriz de tamaño variable
vector<vector<int>> adj(n);  // n filas vacías (útil para grafos)

Acceso

// Acceder a elemento
int valor = matriz[fila][columna];

// Agregar fila
matriz.push_back(vector<int>{1, 2, 3});

// Agregar a lista de adyacencia
adj[u].push_back(v);

Recorrer matriz

int filas = matriz.size();
int columnas = matriz[0].size();

for (int i = 0; i < filas; i++) {
    for (int j = 0; j < columnas; j++) {
        cout << matriz[i][j] << " ";
    }
    cout << endl;
}

Técnicas útiles

Prefijos y sufijos

vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();

// Suma de prefijos
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// prefix = {0, 1, 3, 6, 10, 15}

// Suma del rango [l, r]
int suma = prefix[r + 1] - prefix[l];

Two pointers

// Ejemplo: encontrar par que sume a target en array ordenado
bool encontrarPar(vector<int>& arr, int target) {
    int izq = 0;
    int der = arr.size() - 1;

    while (izq < der) {
        int suma = arr[izq] + arr[der];
        if (suma == target) return true;
        if (suma < target) izq++;
        else der--;
    }

    return false;
}

Sliding window

// Ejemplo: suma máxima de k elementos consecutivos
int maxSumaK(vector<int>& arr, int k) {
    int n = arr.size();
    int sumaVentana = 0;

    // Calcular suma de primera ventana
    for (int i = 0; i < k; i++) {
        sumaVentana += arr[i];
    }

    int maxSuma = sumaVentana;

    // Deslizar ventana
    for (int i = k; i < n; i++) {
        sumaVentana += arr[i] - arr[i - k];
        maxSuma = max(maxSuma, sumaVentana);
    }

    return maxSuma;
}

Funciones útiles de STL

#include <algorithm>
#include <numeric>

vector<int> v = {5, 2, 8, 1, 9};

// Encontrar elemento
auto it = find(v.begin(), v.end(), 8);  // Iterador al 8

// Min y max
int minimo = *min_element(v.begin(), v.end());  // 1
int maximo = *max_element(v.begin(), v.end());  // 9

// Suma total
int suma = accumulate(v.begin(), v.end(), 0);  // 25

// Contar ocurrencias
int cuenta = count(v.begin(), v.end(), 5);  // 1

// Reversar
reverse(v.begin(), v.end());

// Único (requiere estar ordenado)
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());  // Elimina duplicados

// Rotar
rotate(v.begin(), v.begin() + 2, v.end());

Ejercicio práctico

Problema: Dado un array, encuentra el subarreglo contiguo de suma máxima (Kadane's Algorithm).

int maxSubarraySum(vector<int>& arr) {
    // Tu código aquí
}

int maxSubarraySum(vector<int>& arr) {
    int maxActual = arr[0];
    int maxGlobal = arr[0];

    for (int i = 1; i < arr.size(); i++) {
        maxActual = max(arr[i], maxActual + arr[i]);
        maxGlobal = max(maxGlobal, maxActual);
    }

    return maxGlobal;
}

Problemas para practicar

1. Suma de Intervalos - omegaUp
2. Books - Codeforces
3. Subarray Sums I - CSES

Siguiente paso

Continúa aprendiendo sobre pilas y colas para expandir tu conocimiento de estructuras de datos.