Algorithmen und Datenstrukturen · Middle · Frage 56 von 75
Wie beantwortet man auf einem statischen Array viele Male „Summe der Elemente von i bis j“?
- 1Das Array sortieren und für jede Abfrage binär suchen
- 2Einmal Präfixsummen, dann
prefix[j + 1] - prefix[i]pro Abfrage - 3Die Summe für jede einzelne Abfrage per Schleife neu berechnen
Antwort zeigen
Richtige Antwort: Einmal Präfixsummen, dann prefix[j + 1] - prefix[i] pro Abfrage
Erklärung
Die Vorverarbeitung ist O(n) und jede Abfrage O(1). Ändert sich das Array zwischen den Abfragen, brechen Präfixsummen, und man braucht einen Fenwick- oder Segmentbaum.