Python-Set kann ein Set verwalten, aber da das Element keinen Index enthält, kann die Operation "Das x-te Element vom kleinsten ausgeben" nur mit $ O (N) $ für die Anzahl der Elemente N ausgeführt werden. nicht.
Ah, es ist zu spät.
Zusammenfassend ergibt der binär indizierte Baum und die Dichotomie $ O ((logN) ^ 2) $. Ich bin mir nicht sicher, ob es schneller gemacht werden kann.
Vielen Dank, dass Sie auf Mr. Salmonize und Mr. Joe hingewiesen haben. Obwohl es sich um $ O ((logN) ^ 2) $ handelt, benötigt der Dichotomieteil durch Anwenden der Dichotomie auf BIT keine Abfrageverarbeitung von BIT und wird auf $ O (logN) $ beschleunigt.
Bereiten Sie einen Binary Indexed Tree (BIT) vor. Was? Sie kennen BIT nicht? https://ja.wikipedia.org/wiki/フェニック木
Nehmen wir an, wir fügen dem x-ten Element von BIT +1 hinzu, wenn wir der Menge x hinzufügen. Zum Beispiel möchte ich eine Menge von {3, 1, 4} machen! Wenn du denkst
+1 zum dritten Element des BIT-Arrays +1 zum ersten Element des BIT-Arrays +1 bis zum 4. Element des BIT-Arrays
Das ist in Ordnung.
Betrachten wir nun lower_bound. Suche zwei Minuten lang. Wenn Sie das x-te Element vom kleinsten wollen
Wenn Sie eine Dichotomie mit dem Urteil "Gibt es x oder mehr Elemente kleiner oder gleich y?" Durchführen, können Sie die Anzahl der Elemente kleiner oder gleich y in $ O (logN) $ in BIT finden.
Da die Dichotomie selbst $ O (logN) $ kostet
Die Summe ist $ O ((logN) ^ 2) $. Aha.
Wenn Sie mit Floats und Strs umgehen möchten, müssen Sie etwas entwickeln. Wenn es float ist, können Sie die ursprüngliche Zahl mit einer konstanten Zahl multiplizieren, und str kann den Zeichencode verwenden, aber es sieht nicht praktisch aus.
Es ist möglicherweise auch anfällig für Online-Abfragen, da es nicht so stark ist, wie Sie es für dynamische Änderungen halten. Selbst wenn eine große Anzahl gespeichert wird, funktioniert dies nur, wenn eine Koordinatenkomprimierung durchgeführt wird.
Nun, es ist schneller als über eine Ordnungsmenge mit Menge nachzudenken ... Der Suchbaum für die Gleichgewichtshalbierung scheint bequemer zu sein (Ende)
Ich habe den Code übrigens nicht geschrieben.