מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/אלגוריתמים למיון בזמן לינארי/תרגילים/שאילתות על מספר איברים בתחום/שאלה

נתון מערך A המכיל $\displaystyle n$ מספרים, כל אחד בתחום $\displaystyle [1,...,k]$‏ ($\displaystyle k$ מספר שלם כלשהו). רוצים לענות מספר רב של פעמים על שאלות מהסוג: בהינתן $\displaystyle a$ ו$\displaystyle b$ כלשהם, כמה מ$\displaystyle n$ האיברים בA נמצאים בתחום $\displaystyle [a,...,b]$? לצורך כך רוצים לכתוב שתי פונקציות:

1. Init מקבלת את המערך A והערך $\displaystyle k$, ומבצעת פעולות אתחול כלשהן.
2. Range מקבלת שני מספרים a וb, ומחזירה כמה מאיברי A נמצאים בין שני המספרים.להלן דוגמה לשימוש אפשרי:

1	A = [1, 3, 2, 3, 3, 3, 15, 3]

	# Initializes whatever is needed
2	Init(A, 15)

	# Prints 8.
3	Print( Range(1, 16) )

	# Prints 1.
4	Print( Range(1, 1) )

	# Prints 1.
5	Print( Range(2, 2) )

	# Prints 7.
6	Print( Range(1, 14) )

אנא כתוב מימוש יעיל ככל האפשר לשתי הפונקציות, ונתח אותן. (נסה להגיע לכך שRange בזמן $\displaystyle O(1)$.) הוסף משתנים גלובליים ופונקציות עזר כרצונך.