Esta referência fornece implementações concisas de algoritmos e estruturas de dados frequentemente encontrados em competições de programação como CSP-S e NOIP, seguindo um currículo semelhante ao da NOI.

Estruturas de Dados

Fila Monotônica (Sliding Window)

Uma fila monotônica mantém elementos em uma ordem específica (crescente ou decrescente) para encontrar máximos ou mínimos em uma janela deslizante de tamanho fixo.

#include <iostream>
#include <deque>
using namespace std;

void process_window(int data[], int n, int k, bool find_max) {
    deque<int> indices;
    for (int idx = 0; idx < n; ++idx) {
        // Remove índices fora da janela atual
        while (!indices.empty() && indices.front() <= idx - k)
            indices.pop_front();

        // Remove do final os elementos que perdem a monotonicidade
        if (find_max) {
            while (!indices.empty() && data[indices.back()] <= data[idx])
                indices.pop_back();
        } else {
            while (!indices.empty() && data[indices.back()] >= data[idx])
                indices.pop_back();
        }
        indices.push_back(idx);

        // Quando a janela estiver cheia, imprime o extremo
        if (idx >= k - 1)
            cout << data[indices.front()] << " ";
    }
    cout << endl;
}

int main() {
    int n, k;
    cin >> n >> k;
    int arr[1000005];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    process_window(arr, n, k, false); // Mínimos
    process_window(arr, n, k, true);  // Máximos
}

Tabela de Espaçamento (ST Table)

Uma tabela de espaçamento permite consultas idempotentes (como mínimo ou máximo em um intervalo) em tempo O(1) após pré-processamento O(n log n).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int LOG = 21;
int st[MAXN][LOG];

int query_range(int left, int right) {
    int len = right - left + 1;
    int k = log2(len);
    return max(st[left][k], st[right - (1 << k) + 1][k]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int num_elements, num_queries;
    cin >> num_elements >> num_queries;

    for (int i = 0; i < num_elements; ++i)
        cin >> st[i][0];

    for (int power = 1; (1 << power) <= num_elements; ++power)
        for (int start = 0; start + (1 << power) - 1 < num_elements; ++start)
            st[start][power] = max(st[start][power-1], st[start + (1 << (power-1))][power-1]);

    for (int q = 0; q < num_queries; ++q) {
        int l, r;
        cin >> l >> r;
        cout << query_range(l-1, r-1) << '\n';
    }
}

Union-Find (Disjoint Set Union)

O Union-Find é uma estrutura para gerenciar elementos particionados em conjuntos disjuntos, com operações eficientes de unir conjuntos e encontrar o representante de um elemento.

#include <iostream>
using namespace std;
const int MAX_N = 10010;
int parent[MAX_N];

int find_set(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find_set(parent[v]); // Compressão de caminho
}

void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) parent[b] = a;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) parent[i] = i;
    for (int i = 0; i < m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) unite_sets(x, y);
        else cout << (find_set(x) == find_set(y) ? "Y\n" : "N\n");
    }
}

Árvore de Intervalo (Segment Tree)

Uma árvore de intervalo suporta consultas de intervalo e atualizações pontuais ou de intervalo em tempo O(log n).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
ll data_arr[MAXN], tree[4 * MAXN], lazy[4 * MAXN];

void push_up(int node) {
    tree[node] = tree[node*2] + tree[node*2+1];
}

void apply_lazy(int node, int seg_len, ll val) {
    lazy[node] += val;
    tree[node] += seg_len * val;
}

void push_down(int node, int left, int right) {
    if (lazy[node]) {
        int mid = (left + right) / 2;
        apply_lazy(node*2, mid - left + 1, lazy[node]);
        apply_lazy(node*2+1, right - mid, lazy[node]);
        lazy[node] = 0;
    }
}

void build(int node, int left, int right) {
    if (left == right) {
        tree[node] = data_arr[left];
        return;
    }
    int mid = (left + right) / 2;
    build(node*2, left, mid);
    build(node*2+1, mid+1, right);
    push_up(node);
}

ll query_range(int node, int seg_l, int seg_r, int ql, int qr) {
    if (ql <= seg_l && seg_r <= qr) return tree[node];
    push_down(node, seg_l, seg_r);
    int mid = (seg_l + seg_r) / 2;
    ll result = 0;
    if (ql <= mid) result += query_range(node*2, seg_l, mid, ql, qr);
    if (qr > mid) result += query_range(node*2+1, mid+1, seg_r, ql, qr);
    return result;
}

void update_range(int node, int seg_l, int seg_r, int ql, int qr, ll val) {
    if (ql <= seg_l && seg_r <= qr) {
        apply_lazy(node, seg_r - seg_l + 1, val);
        return;
    }
    push_down(node, seg_l, seg_r);
    int mid = (seg_l + seg_r) / 2;
    if (ql <= mid) update_range(node*2, seg_l, mid, ql, qr, val);
    if (qr > mid) update_range(node*2+1, mid+1, seg_r, ql, qr, val);
    push_up(node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> data_arr[i];
    build(1, 1, n);
    for (int i = 0; i < m; ++i) {
        int op, l, r;
        ll k;
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> k;
            update_range(1, 1, n, l, r, k);
        } else {
            cin >> l >> r;
            cout << query_range(1, 1, n, l, r) << endl;
        }
    }
}

Árvore de Fenwick (Binary Indexed Tree)

A Árvore de Fenwick é uma estrutura de dados que suporta consultas de soma de prefixo e atualizações pontuais em tempo O(log n), com menor overhead de memória que uma árvore de intervalo.

#include <iostream>
using namespace std;
const int MAXN = 2000010;
int fenw[MAXN], n;

int lowbit(int x) { return x & -x; }

void add_point(int idx, int delta) {
    for (; idx <= n; idx += lowbit(idx))
        fenw[idx] += delta;
}

int sum_prefix(int idx) {
    int total = 0;
    for (; idx > 0; idx -= lowbit(idx))
        total += fenw[idx];
    return total;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        add_point(i, val);
    }
    for (int i = 0; i < m; ++i) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) add_point(a, b);
        else cout << sum_prefix(b) - sum_prefix(a-1) << endl;
    }
}

Trie (Árvore de Prefixos)

Uma Trie é uma árvore usada para armazenar um dicionário de strings, permitindo buscas, inserções e contagens de prefixos eficientes.

#include <bits/stdc++.h>
using namespace std;
const int CHAR_SET_SIZE = 62; // 0-9, A-Z, a-z

int get_char_index(char c) {
    if (c >= 'A' && c <= 'Z') return c - 'A';
    if (c >= 'a' && c <= 'z') return c - 'a' + 26;
    return c - '0' + 52;
}

struct TrieNode {
    int children[CHAR_SET_SIZE] = {0};
    int count = 0;
};

vector<TrieNode> trie(1);

void insert_string(const string& s) {
    int node = 0;
    for (char c : s) {
        int idx = get_char_index(c);
        if (trie[node].children[idx] == 0) {
            trie[node].children[idx] = trie.size();
            trie.emplace_back();
        }
        node = trie[node].children[idx];
        trie[node].count++;
    }
}

int count_prefix(const string& s) {
    int node = 0;
    for (char c : s) {
        int idx = get_char_index(c);
        if (trie[node].children[idx] == 0) return 0;
        node = trie[node].children[idx];
    }
    return trie[node].count;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        trie.clear();
        trie.emplace_back();
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            insert_string(s);
        }
        for (int i = 0; i < q; ++i) {
            string s;
            cin >> s;
            cout << count_prefix(s) << endl;
        }
    }
}

Algoritmos em Grafos

Busca em Largura (BFS) para Checar Bipartição

const int MAXN = 1005;
int color[MAXN];
vector<int> adj[MAXN];

bool is_bipartite(int start, int n) {
    queue<int> q;
    color[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false;
            }
        }
    }
    return true;
}

Emparelhamento Máximo em Grafo Bipartido (Algoritmo de Kuhn)

#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 10005;
vector<int> graph[MAXN];
int match[MAXN];
bool visited[MAXN];

bool dfs(int u) {
    for (int v : graph[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int max_matching(int n, int m, int edges) {
    memset(match, -1, sizeof(match));
    int result = 0;
    for (int u = 1; u <= n; ++u) {
        memset(visited, 0, sizeof(visited));
        if (dfs(u)) result++;
    }
    return result;
}

Ordenação Topológica

#include <queue>
#include <vector>
using namespace std;

vector<int> topo_sort(int n, const vector<vector<int>>& adj) {
    vector<int> in_degree(n+1, 0);
    for (int u = 1; u <= n; ++u)
        for (int v : adj[u])
            in_degree[v]++;

    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (in_degree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--in_degree[v] == 0)
                q.push(v);
        }
    }
    return order;
}

Caminho Mais Curto (Dijkstra com Fila de Prioridade)

#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MAXN = 200005;

vector<pii> adj[MAXN];
int dist[MAXN];

void dijkstra(int start, int n) {
    fill(dist+1, dist+n+1, INF);
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

Componentes Fortemente Conexos (Algoritmo de Kosaraju)

#include <stack>
#include <vector>
using namespace std;

void dfs1(int u, const vector<vector<int>>& graph, vector<bool>& visited, stack<int>& order) {
    visited[u] = true;
    for (int v : graph[u])
        if (!visited[v]) dfs1(v, graph, visited, order);
    order.push(u);
}

void dfs2(int u, const vector<vector<int>>& rev_graph, vector<bool>& visited, vector<int>& component) {
    visited[u] = true;
    component.push_back(u);
    for (int v : rev_graph[u])
        if (!visited[v]) dfs2(v, rev_graph, visited, component);
}

vector<vector<int>> kosaraju(int n, const vector<vector<int>>& graph) {
    vector<vector<int>> rev_graph(n+1);
    for (int u = 1; u <= n; ++u)
        for (int v : graph[u])
            rev_graph[v].push_back(u);

    vector<bool> visited(n+1, false);
    stack<int> order;
    for (int i = 1; i <= n; ++i)
        if (!visited[i]) dfs1(i, graph, visited, order);

    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
    while (!order.empty()) {
        int u = order.top(); order.pop();
        if (!visited[u]) {
            vector<int> component;
            dfs2(u, rev_graph, visited, component);
            sccs.push_back(component);
        }
    }
    return sccs;
}

Árvore Geradora Mínima (Algoritmo de Kruskal)

#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const { return w < other.w; }
};

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n+1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        parent[y] = x;
        return true;
    }
};

long long kruskal_mst(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total_weight = 0;
    int edges_used = 0;
    for (const Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total_weight += e.w;
            edges_used++;
            if (edges_used == n-1) break;
        }
    }
    return total_weight;
}

Componentes Bi-conexos (BCC) e Pontes

#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> bccs;
stack<int> node_stack;
int timer = 0;

void dfs_tarjan(int u, int parent, const vector<vector<int>>& adj,
                vector<int>& disc, vector<int>& low, vector<bool>& is_bridge) {
    disc[u] = low[u] = ++timer;
    node_stack.push(u);
    int children = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (!disc[v]) {
            children++;
            dfs_tarjan(v, u, adj, disc, low, is_bridge);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                is_bridge[...] = true; // Marca a aresta u-v como ponte
                // Coleta o BCC
                vector<int> bcc;
                int w;
                do {
                    w = node_stack.top(); node_stack.pop();
                    bcc.push_back(w);
                } while (w != v);
                bcc.push_back(u);
                bccs.push_back(bcc);
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

Algoritmos de Sequências e Programação Dinâmica

Subsequência Crescente Máxima (LIS) - O(n log n)

#include <vector>
#include <algorithm>
using namespace std;

int length_of_lis(const vector<int>& nums) {
    vector<int> lis;
    for (int x : nums) {
        auto it = lower_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) lis.push_back(x);
        else *it = x;
    }
    return lis.size();
}

Problema da Mochila (Knapsack) - 0/1

#include <vector>
using namespace std;

int zero_one_knapsack(int capacity, const vector<int>& weights, const vector<int>& values) {
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < weights.size(); ++i) {
        for (int w = capacity; w >= weights[i]; --w) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Matemática Computacional

Exponenciação Rápida

long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

Crivo de Eratóstenes Linear

#include <vector>
using namespace std;

vector<int> primes;
vector<bool> is_composite;

void sieve_linear(int n) {
    is_composite.assign(n+1, false);
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) break;
        }
    }
}

Algoritmo Extendido de Euclides e Inverso Modular

#include <tuple>
using namespace std;

// Retorna (d, x, y) tal que a*x + b*y = d = gcd(a, b)
tuple<long long, long long, long long> extended_gcd(long long a, long long b) {
    if (b == 0) return {a, 1, 0};
    auto [d, x, y] = extended_gcd(b, a % b);
    return {d, y, x - (a / b) * y};
}

long long mod_inverse(long long a, long long m) {
    auto [d, x, y] = extended_gcd(a, m);
    if (d != 1) return -1; // Inverso não existe
    return (x % m + m) % m;
}

Números Combinatórios (Coeficiente Binomial)

#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

long long power_mod(long long base, long long exp, long long mod); // Definido anteriormente

vector<long long> fact, inv_fact;

void precompute_factorials(int max_n) {
    fact.resize(max_n + 1);
    inv_fact.resize(max_n + 1);
    fact[0] = 1;
    for (int i = 1; i <= max_n; ++i)
        fact[i] = (fact[i-1] * i) % MOD;
    inv_fact[max_n] = power_mod(fact[max_n], MOD - 2, MOD);
    for (int i = max_n - 1; i >= 0; --i)
        inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}