Geben Sie Pseudocode an, der es ermöglicht, für n ganze Zahlen aus [0,...,k] nach einem Vorverarbeitungsschritt Anfragen der Form anzahl(a, b) in konstanter Zeit zu beantworten. anzahl(a, b) soll ausgeben, wieviele der Eingabezahlen im Bereich [a,b] liegen. Der Vorverarbeitungsschritt sollte Zeit Θ(n + k) benötigen.
Ich weiss leider nicht wie ich da vorgehen muss, meine Idee war einfach das Count Array zu nehmen es dann von C[a] bis C[b] durchzugehen und zu checken ob eine 1 drin vorkommt oder nicht, wenn ja den Zähler erhöhen, sodass ich bei der Methode anzahl(a, b) auf diesen Zähler zurückgreifen kann. Macht das Sinn?
Kann mir jemand seine Implementation des Pseudo-Codes durchgeben und erklären? Vielen Dank im voraus.
