Inwersje z BIT
Wydajne zliczanie par poza kolejnością
Inwersje z BIT to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Czym jest inwersja
Inwersja to para i < j, dla której a[i] > a[j]. Jest to pojedyncza para elementów występujących w niewłaściwej kolejności, a ich liczba mierzy stopień nieuporządkowania tablicy.
Dlaczego inwersje mają znaczenie
Liczba inwersji jest równa liczbie zamian, które wykonałoby sortowanie bąbelkowe. Zadania konkursowe ukrywają ten problem między innymi w pytaniach o rangi i nieuporządkowanie.
Naiwne zliczanie jest zbyt wolne
Sprawdzenie każdej pary ma złożoność O(n^2). Dla n równego około 100000 oznacza to dziesięć miliardów sprawdzeń, czyli znacznie więcej, niż pozwala limit czasu. Potrzebne jest sprytniejsze rozwiązanie. 🐢
Pomysł z BIT-em
Proszę przejść od lewej do prawej i pytać: ile wcześniejszych elementów jest większych od bieżącego? Drzewo Fenwicka odpowiada na to pytanie na bieżąco.
Zliczanie częstości
BIT przechowuje tablicę częstości wartości. Wywołanie update(v, 1) zapisuje, że wartość v pojawiła się już podczas przejścia.
update(v, 1)Większe wartości tworzą sufiks
Wcześniejsze wartości większe od v to liczba wszystkich dotychczas napotkanych wartości pomniejszona o liczbę wartości nie większych niż v. Dla i-tego elementu jest to i minus query(v).
inv += i - query(v)Kompresja współrzędnych
Jeśli wartości są duże lub ujemne, proszę najpierw przypisać im rangi od 1 do n. Taka kompresja pozwala zachować mały rozmiar BIT-u bez zmiany kolejności wartości.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}Pełne przejście
Proszę przejść po tablicy, dodać każdą policzoną większą wartość do sumy, a następnie wstawić bieżącą wartość. Bieżąca suma jest liczbą inwersji.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Złożoność n log n
Każdy element wywołuje jedno zapytanie i jedną aktualizację, z których każda ma złożoność O(log n). Całe zliczanie kończy się w czasie O(n log n). 🚀
Sortowanie przez scalanie jest spokrewnioną metodą
Sortowanie przez scalanie również zlicza inwersje w czasie O(n log n), podczas etapu scalania. Wersja z BIT-em jest często krótsza do napisania pod presją czasu.
Uwaga na przepełnienie licznika
Liczba inwersji może osiągnąć około n² / 2, czyli bardzo dużą wartość. Liczby całkowite w Pythonie nie mają ograniczonego rozmiaru, ale w innych językach potrzebny byłby typ 64-bitowy.
Szybki test
Proszę sprawdzić, czy rozumie Pan/Pani koszt tego przejścia.
Podsumowanie: zliczanie nieuporządkowania
Policzył(a) Pan/Pani inwersje w czasie O(n log n), przechodząc od lewej do prawej i pytając BIT, ile większych wartości pojawiło się wcześniej. W razie potrzeby proszę skompresować wartości. ✅
Często zadawane pytania
Czy lekcja „Inwersje z BIT” jest bezpłatna?
Tak — pełny tekst „Inwersje z BIT” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Inwersje z BIT”?
Wydajne zliczanie par poza kolejnością Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Inwersje z BIT”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Drzewo Fenwicka dla sum prefiksowych
- Inwersje z BIT
- Drzewo przedziałowe: budowanie i zapytania
- Leniwa propagacja aktualizacji zakresów