Tablica i jej granice

🎯 Po co Ci to?

Tablica (lista) to Twój stary znajomy — używasz jej od działu 3. Ale znajomy ma charakter, który dopiero teraz nazwiemy: jest genialna w jednych operacjach i beznadziejna w innych, a wybór struktury danych polega właśnie na dopasowaniu tego charakteru do zadania. A w rozszerzeniu czeka sztuczka — sumy prefiksowe — pokazująca w pigułce filozofię całego działu: policz coś raz zawczasu, żeby potem odpowiadać błyskawicznie. To ta sama myśl, co przy sortowaniu przed wyszukiwaniem binarnym (6.2), tylko w nowym przebraniu.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• wskazać, które operacje na tablicy są tanie (dostęp po indeksie), a które drogie (wstawianie w środek);
• dobrać strukturę do dominującej operacji, zamiast używać tablicy do wszystkiego;
• (w rozszerzeniu) zbudować sumy prefiksowe i odpowiadać nimi na pytania o sumę fragmentu w stałym czasie.

🔁 Przypomnij sobie

Z 3.4: tablica, indeksy od zera, dostęp L[i], wstawianie/usuwanie; z 6.4: wstawienie w środek przesuwa ogon; z 8.5: suma fragmentu (Kadane).

📘 Wyjaśnienie

📐 DEFINICJA — struktura danych: sposób ułożenia danych w pamięci wraz ze zbiorem operacji, które można na nich wykonać, i ich kosztami.

Po ludzku: nie sama zawartość, ale i naczynie — a naczynie decyduje, co łatwo nalać, a co wylać. Czym NIE jest: pojedynczą wartością ani „typem". Struktura danych to układ + operacje: ta sama zawartość ułożona jako tablica i jako lista wiązana (9.3) to dwie różne struktury o różnych mocnych stronach.

Charakter tablicy. Tablica trzyma elementy pod kolejnymi adresami w pamięci — i stąd wynika wszystko:

• Dostęp po indeksie: błyskawiczny ($O(1)$). L[5000] to jedno działanie: adres początku + 5000. Komputer nie „przechodzi" po elementach — liczy adres i sięga wprost. To supermoc tablicy.
• Wstawianie/usuwanie na końcu: tanie (zwykle $O(1)$). Dokładasz za ostatnim, nic nie przesuwasz.
• Wstawianie/usuwanie w środku: drogie ($O(n)$). Żeby wstawić element na pozycję 3 w tablicy tysiąca, musisz przesunąć 997 elementów o jedno w prawo — bo adresy muszą pozostać kolejne (6.4 wiedziało to już przy sortowaniu przez wstawianie!).

Ten charakter czyni tablicę idealną tam, gdzie dużo się czyta po indeksie, mało wstawia w środek: obraz (piksel [i][j]), tabela wyników, bufor dźwięku. I fatalną tam, gdzie ciągle się wstawia i usuwa w środku — na to jest lista wiązana (9.3). Wybór to nie gust, to dopasowanie: jaka operacja dominuje?

💭 Pomyśl: Prowadzisz listę oczekujących: ludzie dochodzą na koniec, a obsługujesz zawsze pierwszego (usuwasz z początku). Czy tablica to dobra struktura? Co jest w niej drogie?

Sprawdź odpowiedź

Kiepska: usuwanie z początku wymaga przesunięcia wszystkich pozostałych o jedno w lewo — $O(n)$ przy każdym obsłużonym kliencie. Dochodzenie na koniec jest tanie, ale usuwanie z przodu zabija. To wołanie o strukturę „pierwszy wchodzi, pierwszy wychodzi" bez przesuwania — czyli kolejkę (9.3). Rozpoznanie „tablica tu zawadza" jest cenniejsze niż znajomość lekarstwa: gdy operacja jest systematycznie droga, zmień strukturę, nie optymalizuj przesuwanie.

[R] Sumy prefiksowe — policz raz, odpowiadaj w mgnieniu. Masz tablicę dziennych przychodów i sypią się pytania: „ile utargu od dnia 3 do 9?", „a od 100 do 200?", setki takich zapytań. Naiwnie każde to sumowanie fragmentu — $O(n)$ na pytanie. Sztuczka: policz raz tablicę sum prefiksowych, gdzie $P[i]$ = suma wszystkich elementów do pozycji $i$:

def prefiksy(L):
    P = [0] * (len(L) + 1)
    for i in range(len(L)):
        P[i + 1] = P[i] + L[i]        # każdy prefiks z poprzedniego
    return P

Teraz suma fragmentu od $a$ do $b$ (włącznie) to jedno odejmowanie: $P[b+1] - P[a]$ — bo to „suma do $b$" minus „suma przed $a$". Pytanie, które kosztowało $O(n)$, kosztuje $O(1)$!

Koszt: $O(n)$ na przygotowanie (raz), potem $O(1)$ na każde pytanie. Dla tysiąca zapytań o fragmenty: naiwnie milion operacji, prefiksami — tysiąc plus tysiąc. To dokładnie ta sama filozofia, co sortowanie-przed-wyszukiwaniem (6.2) i memoizacja (8.3): przenieś pracę na etap przygotowania, żeby zapytania były darmowe. Sumy prefiksowe to jej najczystszy, jednolinijkowy przykład — i cegiełka pod dziesiątki algorytmów (obrazy całkowe w grafice, szybkie średnie kroczące, zliczanie na przedziałach).

🐞 Znajdź błąd

Program ma usuwać z tablicy wszystkie zera, przechodząc po niej i wywołując L.pop(i) (usuń element o indeksie $i$), gdy L[i] == 0:

def usun_zera(L):
    for i in range(len(L)):
        if L[i] == 0:
            L.pop(i)
    return L

Dla [1, 0, 0, 2] daje [1, 0, 2] — jedno zero zostało! Co się dzieje?

Sprawdź odpowiedź

Po L.pop(1) (usunięcie pierwszego zera) tablica to [1, 0, 2], a pozostałe elementy przesunęły się w lewo — drugie zero, które było na indeksie 2, jest teraz na indeksie 1. Ale pętla idzie dalej na indeks 2 (już 2), przeskakując zero. Usuwanie w środku podczas przechodzenia przesuwa indeksy pod nogami pętli — ten sam błąd, o którym ostrzegał 3.4 (zadanie 3)! Lekcja podwójna: (1) usuwanie w środku tablicy jest nie tylko drogie, ale i zdradliwe podczas iteracji; (2) rozwiązanie to budowanie nowej tablicy z niezerowych elementów — tanio i bezpiecznie. Charakter struktury (drogie usuwanie w środku) rzutuje na to, jak wolno jej używać.

🛠️ Teraz Ty

Przejrzyj trzy swoje programy z działów 3–6 i dla każdego wskaż: gdzie tablica była czytana po indeksie (jej żywioł), a gdzie coś wstawiałeś lub usuwałeś w środku (jej słabość). Czy któryś fragment wołał o inną strukturę?

[R] Bez komputera: dla tablicy [2, 5, 1, 3, 4] policz ręcznie tablicę prefiksów i odpowiedz nimi na: suma od 1 do 3, suma od 0 do 4, suma samego elementu 2. Z komputerem: zaimplementuj prefiksy i funkcję suma_fragmentu(P, a, b); wygeneruj tablicę 100 000 losowych liczb i porównaj czas 1000 zapytań metodą naiwną (sumowanie) i prefiksową.

📐 Definicje tej lekcji

• Struktura danych — układ danych + operacje + ich koszty; dobiera się ją do dominującej operacji.
• Charakter tablicy — dostęp po indeksie $O(1)$, koniec tani, środek drogi ($O(n)$).
• [R] Sumy prefiksowe — $P[i]$ = suma do $i$; suma fragmentu $[a,b]$ = $P[b+1] - P[a]$ w $O(1)$ po przygotowaniu $O(n)$.

📌 Najważniejsze w pigułce

• Struktura to naczynie: ta sama zawartość, różne mocne strony zależnie od układu i operacji.
• Tablica: genialna do czytania po indeksie, kiepska do wstawiania/usuwania w środku — dobieraj do zadania.
• [R] Sumy prefiksowe = „policz raz, odpowiadaj w $O(1)$": ta sama filozofia, co memoizacja i sortowanie-przed-szukaniem.

🎒 Zadania

1. Dla każdej sytuacji oceń, czy tablica to dobry wybór: (a) plansza szachowa 8×8, (b) lista oczekujących w przychodni, (c) historia przeglądarki (cofanie do poprzednich stron), (d) wyniki 1000 zawodników do wielokrotnego czytania po numerze startowym.

Wskazówka i odpowiedź

(a) tablica 2D — idealna: dostęp [i][j] po współrzędnych, nic się nie wstawia w środek. (b) kiepsko — usuwanie z przodu drogie, wołanie o kolejkę (9.3). (c) „cofnij do poprzedniej" to ostatnia-odwiedzona-pierwsza — wołanie o stos (9.2). (d) tablica świetna — same odczyty po indeksie. Trzy z czterech przypadków rozstrzyga jedno pytanie: „jaka operacja dominuje i czy tablica robi ją tanio?".

2. [R] Tablica ocen [3, 5, 4, 6, 2, 5]. Zbuduj prefiksy i policz nimi średnią z ocen od indeksu 1 do 4. Ile operacji zajęłoby to bez prefiksów, a ile z nimi?

Wskazówka i odpowiedź

Prefiksy: [0, 3, 8, 12, 18, 20, 25]. Suma [1,4] = $P[5] - P[1] = 20 - 3 = 17$; średnia $17/4 = 4{,}25$. Bez prefiksów: 4 dodawania (przejście fragmentu). Z prefiksami: 1 odejmowanie (plus dzielenie). Dla fragmentu długości 4 zysk mały, ale dla fragmentu długości 100 000 — 100 000 operacji kontra jedno odejmowanie. Prefiksy opłacają się tym bardziej, im dłuższe fragmenty i im więcej pytań.

3. Zaproponuj, jak sumami prefiksowymi błyskawicznie odpowiadać na pytanie „ile liczb parzystych jest w tablicy od pozycji $a$ do $b$?". Co trzeba wstawić do tablicy prefiksów?

Wskazówka i odpowiedź

Zbuduj prefiksy nie z wartości, lecz z flag parzystości: $F[i] = 1$ jeśli $L[i]$ parzyste, inaczej 0; potem prefiksy tych flag. Liczba parzystych w $[a,b]$ = $P[b+1] - P[a]$. Trik ogólny: sumy prefiksowe liczą nie tylko sumy wartości, ale dowolną addytywną cechę (ile parzystych, ile dodatnich, ile spełniających warunek) — wystarczy zamienić dane na 0/1 wg cechy. To otwiera prefiksy na całą rodzinę pytań „ile w przedziale spełnia…".

🔍 Sprawdź, czy umiesz

• Podać koszty operacji tablicy i dopasować ją (lub odrzucić) do opisanej sytuacji.
• [R] Zbudować sumy prefiksowe i odpowiedzieć nimi na pytanie o sumę fragmentu w $O(1)$.
• Wyjaśnić, czemu usuwanie w środku tablicy jest i drogie, i zdradliwe podczas iteracji.

---