Este artigo aborda a solução de um problema clássico de estrutura de dados: realizar operações de atualização de ponto único e consulta de soma de intervalo em uma sequência. O problema exige processar até 500.000 elementos e 500.000 operações, tornando abordagens ingênuas inviáveis. A estrutura de dados escolhida é a árvore segmentada (segment tree), que oferece complexidade O(log n) para ambas as operações.

Descrição do Problema

Dado um array inicial de N inteiros, o programa deve lidar com M operações:

• Atualização (tipo 1): Somar um valor k ao elemanto na posição x.
• Consutla (tipo 2): Retornar a soma dos elementos no intervalo [x, y].

Estrutura da Árvore Segmentada

Cada nó da árvore armazena um intervalo [l, r] e a soma dos elementos nesse intervalo. A árvore é construída recursivamente: nós folha representam um único elemento, e nós internos combinam as somas dos filhos esquerdo e direito.

Variáveis e Constantes

const int MAXN = 5e5 + 10;
int arr[MAXN];

struct Node {
    int left, right;
    int sum;
} seg[4 * MAXN];

Construção da Árvore (build)

void build(int idx, int l, int r) {
    seg[idx].left = l;
    seg[idx].right = r;
    if (l == r) {
        seg[idx].sum = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(idx * 2, l, mid);
    build(idx * 2 + 1, mid + 1, r);
    seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}

Atualização de Ponto Único (update)

Para somar k ao elemento na posição pos, percorremos a árvore recursivamente. Se o intervalo do nó contém pos, adicionamos k à soma do nó. Continuamos descendo até atingir a folha correspondente.

void update(int idx, int pos, int val) {
    if (seg[idx].left > pos || seg[idx].right < pos) return;
    seg[idx].sum += val;
    if (seg[idx].left == seg[idx].right) return; // folha
    update(idx * 2, pos, val);
    update(idx * 2 + 1, pos, val);
}

Consulta de Soma de Intervalo (query)

Para obter a soma no intervalo [ql, qr], verificamos três casos:

• Se o intervalo do nó está totalmente fora de [ql, qr], retornamos 0.
• Se o intervalo do nó está totalmente dentro de [ql, qr], retornamos a soma armazenada.
• Caso contrário, combinamos as consultas recursivas dos filhos.

int query(int idx, int ql, int qr) {
    if (seg[idx].right < ql || seg[idx].left > qr) return 0;
    if (seg[idx].left >= ql && seg[idx].right <= qr) return seg[idx].sum;
    int left_sum = query(idx * 2, ql, qr);
    int right_sum = query(idx * 2 + 1, ql, qr);
    return left_sum + right_sum;
}

Função Principle

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    build(1, 1, n);
    while (m--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            update(1, a, b);
        } else {
            int result = query(1, a, b);
            cout << result << endl;
        }
    }
    return 0;
}

Exemplo de Execução

Entrada:

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

Saída:

14
16

Análise de Complexidade

• Tempo: Construção O(n), cada operação O(log n). Para o limite de 500.000 operações, é eficiente.
• Espaço: O(n) para o array original e O(4n) para a árvore, dentro da memória especificada.

Essa implementação resolve o problema dentro dos limites de tempo e memória, utilizando a estrutura clássica de árvore segmentada para manipulação de intervalos e pontos.