Wir haben eine Herausforderung, wie schnell die Mengen auf dem l...r in der statischen Absorption auf weniger als O(n) zu zählen.
Trennen Sie a bis k Blöcke gleicher Größe und berechnen Sie vorläufig die Summe der Elemente für jeden.
Nun können wir in Reaktion auf die Anfrage auf die Elemente der Masse a fortfahren und sie dem Ergebnis hinzufügen, auch wenn einer der Blöcke innerhalb des Schnittes liegt, können wir die Menge zum Ergebnis hinzufügen und die Elemente dieses Blocks vermissen.
Die maximale Anzahl von Abfrageoperationen bei einem solchen Algorithmus ist n / k + k, daher ist die optimale k gleich der Quadratwurzel von n.