Range Sum Query

Q: Czym jest tablica sum prefiksowych?

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 następnie suma dowolnego zakresu [left, right] wynosi prefix[right+1] - prefix[left] .

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

O(n) na jednokrotne zbudowanie tablicy prefiksowej, a następnie O(1) na każde zapytanie, 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: Co, jeśli tablica może zmieniać się między zapytaniami?

W takim razie tablica prefiksowa nie jest właściwym narzędziem, ponieważ każda aktualizacja przesuwa wszystkie późniejsze sumy i naprawienie ich kosztuje O(n) . Drzewo Fenwicka lub drzewo przedziałowe obsługuje zarówno aktualizację, jak i sumę z zakresu w czasie O(log n) .

Ł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. Polega ono na obliczeniu 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: zakresy do zsumowania, każdy jako para [left, right], gdzie left ≤ right
Zwracainteger-array: suma każdego zakresu, po jednym dla każdego zapytania, 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: Cała tablica sumuje się do 18, dwie ostatnie wartości do 1 + 8 = 9, sam indeks 0 do 2, a indeksy od 1 do 2 do 7 + 1 = 8.

Pytanie dodatkowe

Jeśli liczby tworzą siatkę, a każde zapytanie dotyczy sumy w prostokącie, jak rozszerzyć sumy prefiksowe, aby odpowiadać na każde zapytanie w czasie stałym?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Pojedynczy zakres to pętla, ale każde zapytanie może obejmować większość tablicy, więc osobne sumowanie każdego z nich powtarza te same dodawania. Zsumuj tablicę raz, tworząc sumy prefiksowe, a każdy zakres będzie wymagał tylko jednego odejmowania.

Zsumuj każdy zakres

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

Intuicja

Dla każdego zapytania dodaj do sumy wartości od nums[left] do nums[right]. To poprawne rozwiązanie, ponieważ odczytuje każdą wartość z zakresu, a dla jednego zapytania nie da się zrobić tego lepiej. Zapytanie może obejmować maksymalnie n wartości, więc q zapytań wymaga maksymalnie n × q dodawań: 1.5 × 10^7, gdy n = 10^4 i q = 1500 — niemal wszystkie są powtórzeniami.

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 listy odpowiedzi i zwróć ją 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 [3, -2, 5, 1, -4, 6] otrzymujemy [0, 3, 1, 6, 7, 3, 9].

Zakres [left, right] to suma wszystkich wartości do indeksu right pomniejszona o sumę wszystkich wartości przed indeksem left: prefix[right+1] - prefix[left]. Dla [1, 4] jest to prefix[5] - prefix[1] = 3 - 3 = 0. Początkowe 0 pozwala użyć tego samego wzoru dla zakresu zaczynającego się od indeksu 0. Jedno przejście wykonujące n dodawań tworzy tablicę, a każde zapytanie wymaga potem jednego odejmowania.

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

Zapisanie prefix[right] - prefix[left]. Przy prefix[0] = 0 pomija to nums[right], więc zakres [3, 3] daje w wyniku 0 zamiast 1.
Utworzenie tablicy prefix o takiej samej długości jak nums, przez co prefix[i] zawiera nums[i]. Zakres zaczynający się od 0 wymaga wtedy prefix[-1], który jest poza zakresem, a Python po cichu odczytuje zamiast tego ostatni element.
Zatrzymanie pętli brute force na i < right. Uwzględnione są oba końce, więc suma dla [3, 3] wyniosłaby 0.
W Lua i R, które liczą od 1, zapytanie indeksowane od 0 [left, right] obejmuje elementy od nums[left+1] do nums[right+1], a indeksy prefiksów przesuwają się w ten sam sposób.

Najczęstsze pytania3

Czym jest tablica sum prefiksowych?

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 następnie suma dowolnego zakresu [left, right] wynosi prefix[right+1] - prefix[left].

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

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

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

W takim razie tablica prefiksowa nie jest właściwym narzędziem, ponieważ każda aktualizacja przesuwa wszystkie późniejsze sumy i naprawienie ich kosztuje O(n). Drzewo Fenwicka lub drzewo przedziałowe obsługuje zarówno aktualizację, jak i sumę z zakresu w czasie O(log n).

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

Test #1

Test #2

Argumenty

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

Oczekiwany wynik

[6, 0, 1]