Range Sum Query

Q: O que é um array de soma de prefixos?

É um array em que cada entrada é o total de todos os valores antes de uma posição: prefix[i] = nums[0] + ... + nums[i-1] , com prefix[0] = 0 . Você o constrói em uma única passagem e, depois disso, a soma de qualquer intervalo [left, right] é prefix[right+1] - prefix[left] , uma subtração.

Q: Qual é a complexidade de tempo das consultas de soma em intervalos usando somas de prefixos?

O(n) para construir o array de prefixos uma vez e, depois, O(1) por consulta, resultando em O(n + q) para q consultas. Somar diretamente cada intervalo custa até O(n) por consulta, o que totaliza O(n·q) .

Q: Por que o array de prefixos tem uma entrada a mais do que nums?

O prefix[0] = 0 extra representa o início vazio do array. Com ele, todos os intervalos usam a mesma fórmula, incluindo os que começam no índice 0: prefix[right+1] - prefix[0] . Sem ele, você precisa de uma condição separada para left = 0 .

Q: E se o array puder mudar entre as consultas?

Então, um array de prefixos é a ferramenta errada, porque uma atualização desloca todos os totais posteriores e custa O(n) para corrigir. Uma árvore de Fenwick ou uma árvore de segmentos lida com uma atualização e uma soma em intervalo em O(log n) . Quando o array nunca muda, somas de prefixos simples são mais rápidas e concisas.

FácilSoma de prefixos

+10

Você recebe um array de inteiros nums que nunca muda e uma lista de queries. Cada consulta é um par [left, right] de índices baseados em 0 e pede nums[left] + nums[left+1] + ... + nums[right], incluindo ambas as extremidades. Retorne as respostas na mesma ordem das consultas.

Função

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: o array de números inteiros, o mesmo para todas as consultas
queriesinteger-2d-array: os intervalos a somar, cada um um par [left, right] com left ≤ right
Retornainteger-array: a soma de cada intervalo, uma por consulta, na ordem das consultas

Restrições

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length para cada consulta [left, right]

Exemplos

Entrada: nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
Saída: [6, 0, 1]
Explicação: Os índices de 0 a 2 somam 3 + (-2) + 5 = 6. Os índices de 1 a 4 somam -2 + 5 + 1 + (-4) = 0. O intervalo [3, 3] corresponde ao único valor 1.

Entrada: nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
Saída: [18, 9, 2, 8]
Explicação: A soma do array inteiro é 2 + 7 + 1 + 8 = 18, a dos dois últimos valores é 1 + 8 = 9, a do índice 0 sozinho é 2 e a dos índices de 1 a 2 é 7 + 1 = 8.

+14 testes ocultos ao enviar

Para ir além

Agora, os números formam uma grade, e cada consulta pede a soma de um retângulo definido por dois cantos. Como você estenderia as somas prefixadas para responder a cada consulta com um número constante de operações?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um intervalo é um loop. O problema é a quantidade deles: cada consulta pode abranger a maior parte do array, então somar cada uma separadamente repete as mesmas adições várias vezes. Some tudo uma vez em somas de prefixo, e cada intervalo se torna uma subtração.

Some cada intervalo

Correta, mas não termina nos maiores testes

Intuição

Responda a cada consulta separadamente: comece um total em 0, some nums[left] até nums[right] e armazene o resultado. Para [1, 4] em [3, -2, 5, 1, -4, 6], isso é -2 + 5 + 1 + (-4) = 0.

Está correto e, para uma única consulta, é o melhor que você pode fazer: é preciso ler cada valor do intervalo uma vez. O custo está na repetição. Uma consulta pode abranger até n valores, então q consultas custam até n × q adições. Com n = 10^4 e 1500 consultas que abrangem quase todo o array, isso dá cerca de 1.3 × 10^7 adições, quase todas repetindo trabalho feito para uma consulta anterior.

Além da lista de respostas, ele mantém um total, então o espaço extra é O(1).

Algoritmo

Crie uma lista de respostas vazia.
Para cada consulta [left, right], defina total = 0.
Adicione nums[i] a total para cada i de left a right, incluindo ambos.
Adicione total às respostas e retorne-as após a última consulta.

def sumRange(nums, queries):
    answers = []
    for left, right in queries:
        total = 0
        for i in range(left, right + 1):
            total += nums[i]
        answers.append(total)
    return answers

Somas de prefixo

Intuição

Seja prefix[i] a soma dos primeiros i valores, com prefix[0] = 0 para o início vazio. Para [3, -2, 5, 1, -4, 6], isso resulta em prefix = [0, 3, 1, 6, 7, 3, 9]. Cada elemento é o anterior mais um valor, então o array inteiro exige n adições.

O intervalo [left, right] corresponde a tudo até e incluindo o índice right, menos tudo antes do índice left. Ou seja, prefix[right+1] - prefix[left]. Para [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. Para [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. O 0 inicial é o que permite calcular um intervalo que começa no índice 0 sem um caso especial.

Construir o array custa O(n), e cada consulta custa uma subtração, então o tempo total é O(n + q) e o espaço extra é O(n). Nenhuma soma de prefixo aqui ultrapassa 10^4 × 10^4 = 10^8, então inteiros de 32 bits são suficientes.

Algoritmo

Crie prefix com comprimento n+1 e prefix[0] = 0.
Para cada i de 0 a n-1, defina prefix[i+1] = prefix[i] + nums[i].
Para cada consulta [left, right], adicione prefix[right+1] - prefix[left] às respostas.
Retorne as respostas.

def sumRange(nums, queries):
    # prefix[i] is the sum of the first i values, so prefix[0] = 0.
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    # nums[left..right] is the first right+1 values minus the first left values.
    return [prefix[right + 1] - prefix[left] for left, right in queries]

Armadilhas e casos extremos

Quase todo bug aqui é um índice com um deslocamento de uma posição.

Escrever prefix[right] - prefix[left]. Com prefix[0] = 0, isso deixa de fora nums[right], então o intervalo [3, 3] retorna 0 em vez do valor no índice 3.
Construir prefix com o mesmo comprimento de nums, fazendo com que prefix[i] inclua nums[i]. Então, um intervalo que começa em 0 precisa de prefix[left-1], que está fora dos limites e, em Python, lê silenciosamente a última entrada. O 0 extra no início elimina esse caso especial.
Parar a força bruta em i < right. As duas extremidades do intervalo estão incluídas.
Esquecer que Lua e R contam a partir de 1. A consulta baseada em 0 [left, right] cobre nums[left+1] até nums[right+1] nessas linguagens, e a diferença do prefixo sofre o mesmo deslocamento.
Usar um total de 32 bits quando os valores ou os comprimentos aumentam. Aqui, a maior soma é 10^8, mas, com valores próximos de 10^9, uma soma de prefixos transborda rapidamente, e um array de 64 bits é a opção padrão mais segura.

Perguntas frequentes4

O que é um array de soma de prefixos?

É um array em que cada entrada é o total de todos os valores antes de uma posição: prefix[i] = nums[0] + ... + nums[i-1], com prefix[0] = 0. Você o constrói em uma única passagem e, depois disso, a soma de qualquer intervalo [left, right] é prefix[right+1] - prefix[left], uma subtração.

Qual é a complexidade de tempo das consultas de soma em intervalos usando somas de prefixos?

O(n) para construir o array de prefixos uma vez e, depois, O(1) por consulta, resultando em O(n + q) para q consultas. Somar diretamente cada intervalo custa até O(n) por consulta, o que totaliza O(n·q).

Por que o array de prefixos tem uma entrada a mais do que nums?

O prefix[0] = 0 extra representa o início vazio do array. Com ele, todos os intervalos usam a mesma fórmula, incluindo os que começam no índice 0: prefix[right+1] - prefix[0]. Sem ele, você precisa de uma condição separada para left = 0.

E se o array puder mudar entre as consultas?

Então, um array de prefixos é a ferramenta errada, porque uma atualização desloca todos os totais posteriores e custa O(n) para corrigir. Uma árvore de Fenwick ou uma árvore de segmentos lida com uma atualização e uma soma em intervalo em O(log n). Quando o array nunca muda, somas de prefixos simples são mais rápidas e concisas.

Python

def sumRange(nums, queries):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

Esperado

[6, 0, 1]