Neste cenário de processamento de dados, lidamos com um conjunto de $N$ elementos (inicialmente zerados) e precisamos realizar dois tipos de operações de forma eficiente: atualizar o valor de um elemento específico (Point Update) e consultar o valor máximo dentro de um intervalo $[L, R]$ (Range Maximum Query - RMQ).

Dado que o número de operações $Q$ e a quantidade de elementos $N$ podem chegar a $10^5$, soluções ingênuas de $O(N)$ por consulta resultariam em um desempenho inaceitável de $O(N \cdot Q)$. Abaixo, exploramos duas estruturas de dados clássicas para resolver este problema com complexidade $O(\log N)$ por operação.

1. Implementação com Árvore de Segmento (Segment Tree)

A Árvore de Segmento é uma das estruturas mais versáteis para consultas de intervalo. Cada nó da árvore armazena o valor máximo do intervalo que ele representa.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 100005;
long long seg_tree[MAX_N * 4];

void modificar(int node, int start, int end, int idx, int val) {
    if (start == end) {
        seg_tree[node] += val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) {
        modificar(2 * node, start, mid, idx, val);
    } else {
        modificar(2 * node + 1, mid + 1, end, idx, val);
    }
    seg_tree[node] = max(seg_tree[2 * node], seg_tree[2 * node + 1]);
}

long long consultar(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        return 0;
    }
    if (l <= start && end <= r) {
        return seg_tree[node];
    }
    int mid = (start + end) / 2;
    return max(consultar(2 * node, start, mid, l, r),
               consultar(2 * node + 1, mid + 1, end, l, r));
}

int main() {
    int n, q;
    while (scanf("%d %d", &n, &q) != EOF) {
        for (int i = 0; i <= 4 * n; i++) seg_tree[i] = 0;
        
        while (q--) {
            int tipo, a, b;
            scanf("%d %d %d", &tipo, &a, &b);
            if (tipo == 1) {
                modificar(1, 1, n, a, b);
            } else {
                printf("%lld\n", consultar(1, 1, n, a, b));
            }
        }
    }
    return 0;
}

2. Implementação com Árvore de Fenwick (Binary Indexed Tree)

Embora a Fenwick Tree seja comumente associada a somas de prefixo, ela pode ser adaptada para consultas de máximo. No entanto, para consultas de intervalos arbitrários $[L, R]$, a lógica exige uma verificação adicional para garantir que não estamos acessando valores fora do escopo desejado.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100005;
long long data_array[MAX_N];
long long bit_max[MAX_N];
int total_n;

inline int obter_lowbit(int i) {
    return i & -i;
}

void atualizar_bit(int pos, int n) {
    while (pos <= n) {
        bit_max[pos] = data_array[pos];
        int lb = obter_lowbit(pos);
        for (int j = 1; j < lb; j <<= 1) {
            bit_max[pos] = max(bit_max[pos], bit_max[pos - j]);
        }
        pos += lb;
    }
}

long long query_max(int l, int r) {
    long long res = 0;
    while (r >= l) {
        res = max(res, data_array[r]);
        r--;
        while (r - obter_lowbit(r) >= l) {
            res = max(res, bit_max[r]);
            r -= obter_lowbit(r);
        }
    }
    return res;
}

int main() {
    int q;
    while (scanf("%d %d", &total_n, &q) != EOF) {
        for (int i = 0; i <= total_n; i++) {
            data_array[i] = 0;
            bit_max[i] = 0;
        }

        while (q--) {
            int op, v1, v2;
            scanf("%d %d %d", &op, &v1, &v2);
            if (op == 1) {
                data_array[v1] += v2;
                atualizar_bit(v1, total_n);
            } else {
                printf("%lld\n", query_max(v1, v2));
            }
        }
    }
    return 0;
}

Considerações Técnicas

• Overflow: Como os danos acumuladso podem ultrapassar o limite de 32 bits ($2 \cdot 10^9$), o uso de long long é obrigatório para evitar erros de precisão.
• Complexidade Espacial: A Árvore de Segmento utiliza aproximadamente $4N$ de memória, enquanto a Fenwick Tree utiliza $N$, sendo mais eficiente em termos de espaço.
• Desempenho: Em termos de tempo de execução, a Árvore de Segmento tende a ser ligeiramente mais lenta devido à recursão e maior número de nós, mas oferece uma implementação mais intuitiva para problemas de RMQ.