Range Sum Query

Q: Czym jest tablica sum prefiksowych?

To tablica, w której każdy element jest sumą wszystkich wartości przed daną pozycją: prefix[i] = nums[0] + ... + nums[i-1] , przy czym prefix[0] = 0 . Budujesz ją w jednym przebiegu, a potem suma dowolnego zakresu [left, right] to prefix[right+1] - prefix[left] , czyli jedno odejmowanie.

Q: Jaka jest złożoność czasowa zapytań o sumę zakresu z użyciem sum prefiksowych?

Jednorazowe zbudowanie tablicy prefiksowej zajmuje O(n) , a następnie każde zapytanie O(1) , czyli O(n + q) dla q zapytań. Bezpośrednie sumowanie każdego zakresu kosztuje do O(n) na zapytanie, czyli łącznie O(n·q) .

Q: Dlaczego tablica prefix ma o jeden element więcej niż nums?

Dodatkowy element prefix[0] = 0 oznacza pusty początek tablicy. Dzięki niemu każdy zakres korzysta z tego samego wzoru, także zakresy zaczynające się od indeksu 0: prefix[right+1] - prefix[0] . Bez niego potrzebujesz osobnej gałęzi dla left = 0 .

Q: A co, jeśli tablica może się zmieniać między zapytaniami?

W takim razie tablica prefiksowa nie jest odpowiednim narzędziem, ponieważ każda aktualizacja przesuwa wszystkie sumy po niej i ich poprawienie kosztuje O(n) . Drzewo Fenwicka lub drzewo przedziałowe obsługuje zarówno aktualizację, jak i sumę przedziału w O(log n) . Gdy tablica nigdy się nie zmienia, zwykłe sumy prefiksowe są szybsze i krótsze.

ŁatweSumy prefiksowe

+10

Otrzymujesz tablicę liczb całkowitych nums, która nigdy się nie zmienia, oraz listę queries. Każde zapytanie to para [left, right] indeksów liczonych od 0 i dotyczy wartości nums[left] + nums[left+1] + ... + nums[right], z uwzględnieniem obu końców. Zwróć odpowiedzi w tej samej kolejności co zapytania.

Funkcja

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

numsinteger-array: tablica liczb całkowitych, taka sama dla każdego zapytania
queriesinteger-2d-array: przedziały do zsumowania, każdy jako para [left, right], gdzie left ≤ right
Zwracainteger-array: suma każdego zakresu, po jednym na zapytanie, w kolejności zapytań

Ograniczenia

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length dla każdego zapytania [left, right]

Przykłady

Wejście: nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
Wyjście: [6, 0, 1]
Wyjaśnienie: Indeksy od 0 do 2 zawierają 3 + (-2) + 5 = 6. Indeksy od 1 do 4 zawierają -2 + 5 + 1 + (-4) = 0. Zakres [3, 3] to pojedyncza wartość 1.

Wejście: nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
Wyjście: [18, 9, 2, 8]
Wyjaśnienie: Suma całej tablicy wynosi 2 + 7 + 1 + 8 = 18, suma dwóch ostatnich wartości to 1 + 8 = 9, sama wartość o indeksie 0 to 2, a suma wartości o indeksach od 1 do 2 to 7 + 1 = 8.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Teraz liczby tworzą siatkę, a każde zapytanie dotyczy sumy prostokąta wyznaczonego przez dwa przeciwległe wierzchołki. Jak rozszerzyć sumy prefiksowe, aby odpowiadać na każde zapytanie w stałej liczbie operacji?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Jeden zakres to pętla. Problemem jest ich liczba: każde zapytanie może obejmować większość tablicy, więc osobne sumowanie każdego z nich powtarza w kółko te same dodawania. Zsumuj wszystko raz, tworząc sumy prefiksowe, a każdy zakres będzie wymagał jednego odejmowania.

Dodaj do siebie wszystkie zakresy

Poprawne, ale nie kończy się na największych testach

Intuicja

Odpowiadaj na każde zapytanie osobno: zacznij od sumy równej 0, dodaj wartości od nums[left] do nums[right] i zapisz wynik. Dla [1, 4] w [3, -2, 5, 1, -4, 6] będzie to -2 + 5 + 1 + (-4) = 0.

To poprawne rozwiązanie, a dla pojedynczego zapytania — najlepsze, jakie możesz uzyskać: musisz raz odczytać każdą wartość z zakresu. Problemem jest powtarzanie obliczeń. Zapytanie może obejmować do n wartości, więc obsłużenie q zapytań wymaga do n × q dodawań. Dla n = 10^4 i 1500 zapytań, z których każde obejmuje większość tablicy, to około 1.3 × 10^7 dodawań, z czego niemal wszystkie powtarzają obliczenia wykonane już dla wcześniejszego zapytania.

Oprócz listy odpowiedzi przechowuje jedną sumę, więc dodatkowa przestrzeń wynosi O(1).

Algorytm

Utwórz pustą listę odpowiedzi.
Dla każdego zapytania [left, right] ustaw total = 0.
Dodaj nums[i] do total dla każdego i od left do right, włącznie.
Dodaj total do odpowiedzi i zwróć je po ostatnim zapytaniu.

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

Sumy prefiksowe

Intuicja

Niech prefix[i] oznacza sumę pierwszych i wartości, przy czym prefix[0] = 0 dla pustego początku. Dla [3, -2, 5, 1, -4, 6] otrzymujemy prefix = [0, 3, 1, 6, 7, 3, 9]. Każdy element to poprzedni element powiększony o jedną wartość, więc utworzenie całej tablicy wymaga n dodawań.

Zakres [left, right] obejmuje wszystkie elementy do indeksu right włącznie, pomniejszone o wszystkie elementy przed indeksem left. Otrzymujemy więc prefix[right+1] - prefix[left]. Dla [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. Dla [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. Początkowe 0 pozwala obsłużyć zakres zaczynający się od indeksu 0 bez szczególnego przypadku.

Utworzenie tablicy kosztuje O(n), a każde zapytanie wymaga potem jednego odejmowania, więc łączny czas wynosi O(n + q), a dodatkowa pamięć O(n). Żadna suma prefiksowa nie przekracza tu wartości 10^4 × 10^4 = 10^8, więc wystarczą liczby całkowite 32-bitowe.

Algorytm

Utwórz prefix o długości n+1 z prefix[0] = 0.
Dla każdego i od 0 do n-1 ustaw prefix[i+1] = prefix[i] + nums[i].
Dla każdego zapytania [left, right] dodaj prefix[right+1] - prefix[left] do odpowiedzi.
Zwróć odpowiedzi.

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]

Pułapki i przypadki brzegowe

Prawie każdy błąd w tym kodzie wynika z przesunięcia indeksu o jeden.

Obliczanie prefix[right] - prefix[left]. Przy prefix[0] = 0 pomija to nums[right], więc zakres [3, 3] zwraca 0 zamiast wartości pod indeksem 3.
Tworzenie prefix o takiej samej długości jak nums, przez co prefix[i] zawiera nums[i]. Wtedy zakres zaczynający się od 0 wymaga użycia prefix[left-1], które jest poza zakresem, a Python po cichu odczytuje ostatni element. Dodatkowe początkowe 0 eliminuje ten szczególny przypadek.
Zatrzymywanie algorytmu brute force przy i < right. Obydwa końce zakresu są uwzględnione.
Zapominanie, że Lua i R liczą od 1. Zapytanie oparte na indeksowaniu od 0, [left, right], obejmuje tam elementy od nums[left+1] do nums[right+1], a różnica sum prefiksowych przesuwa się w ten sam sposób.
Używanie sumy 32-bitowej, gdy wartości lub długości rosną. Tutaj największa suma wynosi 10^8, ale przy wartościach bliskich 10^9 suma prefiksowa szybko przekracza zakres, a tablica 64-bitowa jest bezpiecznym wyborem domyślnym.

Najczęstsze pytania4

Czym jest tablica sum prefiksowych?

To tablica, w której każdy element jest sumą wszystkich wartości przed daną pozycją: prefix[i] = nums[0] + ... + nums[i-1], przy czym prefix[0] = 0. Budujesz ją w jednym przebiegu, a potem suma dowolnego zakresu [left, right] to prefix[right+1] - prefix[left], czyli jedno odejmowanie.

Jaka jest złożoność czasowa zapytań o sumę zakresu z użyciem sum prefiksowych?

Jednorazowe zbudowanie tablicy prefiksowej zajmuje O(n), a następnie każde zapytanie O(1), czyli O(n + q) dla q zapytań. Bezpośrednie sumowanie każdego zakresu kosztuje do O(n) na zapytanie, czyli łącznie O(n·q).

Dlaczego tablica prefix ma o jeden element więcej niż nums?

Dodatkowy element prefix[0] = 0 oznacza pusty początek tablicy. Dzięki niemu każdy zakres korzysta z tego samego wzoru, także zakresy zaczynające się od indeksu 0: prefix[right+1] - prefix[0]. Bez niego potrzebujesz osobnej gałęzi dla left = 0.

A co, jeśli tablica może się zmieniać między zapytaniami?

W takim razie tablica prefiksowa nie jest odpowiednim narzędziem, ponieważ każda aktualizacja przesuwa wszystkie sumy po niej i ich poprawienie kosztuje O(n). Drzewo Fenwicka lub drzewo przedziałowe obsługuje zarówno aktualizację, jak i sumę przedziału w O(log n). Gdy tablica nigdy się nie zmienia, zwykłe sumy prefiksowe są szybsze i krótsze.

Python

def sumRange(nums, queries):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

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

Oczekiwane

[6, 0, 1]