Range Sum Query
Você recebe um array de números inteiros nums que nunca muda e uma lista de queries. Cada consulta é um par [left, right] de índices baseados em 0 e solicita nums[left] + nums[left+1] + ... + nums[right], incluindo as duas extremidades. Retorne as respostas na mesma ordem das consultas.
Função
- numsinteger-array
- o array de inteiros, o mesmo para todas as consultas
- queriesinteger-2d-array
- os intervalos a serem somados, cada um um par [left, right] com left ≤ right
- Retornainteger-array
- a soma de cada intervalo, um por consulta, na ordem das consultas
Restrições
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthpara 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 contêm
3 + (-2) + 5 = 6. Os índices de 1 a 4 contêm-2 + 5 + 1 + (-4) = 0. O intervalo[3, 3]é o valor único1.
- Entrada
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Saída
- [18, 9, 2, 8]
- Explicação
- O array inteiro soma
18, os dois últimos valores somam1 + 8 = 9, somente o índice 0 soma2, e os índices de 1 a 2 somam7 + 1 = 8.
Para ir além
Se os números formam uma grade e cada consulta pede a soma de um retângulo, como você estenderia as somas prefixadas para responder a cada consulta em tempo constante?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Muitas consultas abrangem praticamente os mesmos valores. Que trabalho você poderia fazer uma única vez, antes de ler qualquer consulta?
Se você soubesse o total dos primeiros
ivalores para cadai, um intervalo seria a diferença entre dois desses totais.Construa
prefixcomprefix[0] = 0eprefix[i+1] = prefix[i] + nums[i]. Então, cada consulta[left, right]éprefix[right+1] - prefix[left].
Solução
Um único intervalo é um loop, mas cada consulta pode abranger a maior parte do array, então somar cada um separadamente repete as mesmas adições. Some o array uma vez em somas de prefixos, e cada intervalo se torna uma subtração.
Some cada intervalo
Correta, mas não termina nos maiores testes
Intuição
Para cada consulta, some nums[left] até nums[right] a um total. Isso está correto porque lê todos os valores do intervalo, e para uma consulta é o melhor que você pode fazer. Uma consulta pode abranger até n valores, então q consultas custam até n × q adições: 1.5 × 10^7 quando n = 10^4 e q = 1500, quase todas repetidas.
Algoritmo
- Crie uma lista de respostas vazia.
- Para cada consulta
[left, right], definatotal = 0. - Adicione
nums[i]atotalpara cadaideleftaright, 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 answersSomas de prefixo
Intuição
Seja prefix[i] a soma dos primeiros i valores, com prefix[0] = 0. Para [3, -2, 5, 1, -4, 6], isso resulta em [0, 3, 1, 6, 7, 3, 9].
O intervalo [left, right] corresponde a tudo até o índice right menos tudo o que vem antes do índice left: prefix[right+1] - prefix[left]. Para [1, 4], isso é prefix[5] - prefix[1] = 3 - 3 = 0. O 0 inicial permite que um intervalo que começa no índice 0 use a mesma fórmula. Uma única passagem com n adições constrói o array, e cada consulta passa a ser uma subtração.
Algoritmo
- Crie
prefixcom comprimenton+1eprefix[0] = 0. - Para cada
ide0an-1, definaprefix[i+1] = prefix[i] + nums[i]. - Para cada consulta
[left, right], acrescenteprefix[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
- Escrever
prefix[right] - prefix[left]. Comoprefix[0] = 0, isso deixa de foranums[right], então o intervalo[3, 3]retorna0em vez de1. - Fazer
prefixter o mesmo tamanho quenums, de modo queprefix[i]incluanums[i]. Um intervalo que começa em 0 precisaria então deprefix[-1], que está fora dos limites, e o Python lê silenciosamente a última entrada. - Parar o loop de força bruta em
i < right. As duas extremidades estão incluídas, então[3, 3]não somaria nada. - Em Lua e R, que começam a contagem em 1, a consulta baseada em índices 0
[left, right]abrangenums[left+1]aténums[right+1], e os índices do prefixo se deslocam da mesma forma.
Perguntas frequentes3
O que é um array de soma de prefixos?
Um array em que cada entrada é o total de todos os valores anteriores a uma posição: prefix[i] = nums[0] + ... + nums[i-1], com prefix[0] = 0. Você o constrói em uma única passagem e, então, a soma de qualquer intervalo [left, right] é prefix[right+1] - prefix[left].
Qual é a complexidade de tempo das consultas de soma em intervalos com somas de prefixos?
O(n) para construir o array de prefixos uma vez, depois O(1) por consulta, resultando em O(n + q) para q consultas. Somar cada intervalo diretamente custa até O(n) por consulta, O(n·q) no total.
O que acontece 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 um intervalo em O(log n).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def sumRange(nums, queries):
# Escreva o código aquiTeste #1
Teste #2
Argumentos
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Saída Esperada
[6, 0, 1]