O Problema das Atualizações Baseadas em Passsos

Ao lidar com problemas de estruturas de dados que exigem a adição de um valor $k$ a todos os múltiplos de um determinado número $D$, seguida de consultas de soma em um intervalo $[L, R]$, a escolha ingênua da estrutura de dados frequentemente leva a estouros de limite de tempo. A solução ideal exige o equilíbrio entre o tempo de atualização e o tempo de consulta, algo que pode ser alcançado combinando uma Árvore de Fenwick (Binary Indexed Tree) com a técnica de Decomposição em Raiz Quadrada (Square Root Decomposition).

Abordagem 1: Atualização Direta na Árvore de Fenwick

A ideia mais imediata é iterar por todos os múltiplos de $D$ e atualizar diretamente a Árvore de Fenwick. Durante uma consulta, a árvore responde em tempo logarítmico.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_VAL = 200005;
long long bit[MAX_VAL];
int max_size, queries_count;

void add(int idx, long long val) {
    for (; idx <= max_size; idx += idx & -idx) {
        bit[idx] += val;
    }
}

long long prefix_sum(int idx) {
    long long total = 0;
    for (; idx > 0; idx -= idx & -idx) {
        total += bit[idx];
    }
    return total;
}

long long range_sum(int left, int right) {
    return prefix_sum(right) - prefix_sum(left - 1);
}

Embora as consultas sejam rápidas, $O(\log N)$, a atualização se torna proibitiva quando $D$ é pequeno. Se $D = 1$, a operação exigirá $N$ atualizações na árvore, resultando em uma complexidade de $O(N \log N)$ por operação de atualização, o que causa falha por limite de tempo (TLE) em cenários com muitas operações.

Abordagem 2: Avaliação Preguiçosa (Lazy Evaluation)

Para contornar o problema das atualizações custosas, podemos adiar o processamento. Em vez de atualizar a Árvore de Fenwick, armazenamos o valor a ser adicionado em um vetor auxiliar pending[D] += k. Quando uma consulta no intervalo $[L, R]$ é realizada, iteramos por todos os possíveis passos $i$ de $1$ até $N$, calculando quantos múltiplos de $i$ existem no intervalo e multiplicando pelo valor acumulado em pending[i].

long long process_query_lazy(int L, int R) {
    long long result = range_sum(L, R);
    for (int i = 1; i <= max_size; ++i) {
        if (pending[i] != 0) {
            long long multiples_in_range = (R / i) - ((L - 1) / i);
            result += multiples_in_range * pending[i];
        }
    }
    return result;
}

Esta abordagem inverte o gargalo. As atualizações agora ocorrem em $O(1)$, mas as consultas exigem uma iteração completa até $N$, tornando-as $O(N)$. Se o valor de $D$ for consistentemente grande, o vetor pending se enche e as consultas se tornam extremamente lentas.

Solução Híbrida: Decomposição em Raiz Quadrada

A solução definitiva une os dois métodos usando um limiar baseado na raiz quadrada do tamanho máximo do array, $B = \sqrt{N}$.

• Para passos pequenos ($D \le B$): Utilizamos a avaliação preguiçosa. A atualização é $O(1)$ e, durante a consulta, iteramos apenas até $B$, o que leva $O(\sqrt{N})$.
• Para passos grandes ($D > B$): Atualizamos diretamente a Árvore de Fenwick. Como $D$ é grande, existem no máximo $N/D$ múltiplos, o que equivale a $O(\sqrt{N})$ atualizações. A consulta permanece $O(\log N)$ para a parte da árvore.

Abaixo está a implementação completa integrando essa lógica híbrida:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MAX_VAL = 200005;
long long fenwick_tree[MAX_VAL];
long long lazy_updates[MAX_VAL];
int array_size, total_queries;

void update_fenwick(int idx, long long val) {
    for (; idx <= array_size; idx += idx & -idx) {
        fenwick_tree[idx] += val;
    }
}

long long query_fenwick(int idx) {
    long long sum = 0;
    for (; idx > 0; idx -= idx & -idx) {
        sum += fenwick_tree[idx];
    }
    return sum;
}

long long get_range_sum(int left, int right) {
    return query_fenwick(right) - query_fenwick(left - 1);
}

void execute() {
    if (!(cin >> array_size >> total_queries)) return;
    
    int threshold = sqrt(array_size);
    
    for (int q = 0; q < total_queries; ++q) {
        int operation, param1;
        long long param2;
        cin >> operation >> param1 >> param2;
        
        if (operation == 1) {
            int step = param1;
            long long value_to_add = param2;
            
            if (step <= threshold) {
                lazy_updates[step] += value_to_add;
            } else {
                for (int i = step; i <= array_size; i += step) {
                    update_fenwick(i, value_to_add);
                }
            }
        } else {
            int L = param1;
            int R = param2;
            
            long long final_answer = get_range_sum(L, R);
            
            for (int step = 1; step <= threshold; ++step) {
                if (lazy_updates[step] != 0) {
                    long long count_multiples = (R / step) - ((L - 1) / step);
                    final_answer += count_multiples * lazy_updates[step];
                }
            }
            cout << final_answer << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    execute();
    return 0;
}