Range Count of Ones in a Binary Array (Immutable)

You are given a very large 1D binary array A of length N (values are only 0 or 1). Requirements: You must not modify the array (it is immutable). You need to support many queries on the same array. Implement a method/class to return the number of 1s in any inclusive range [l, r] (0 <= l <= r < N) as fast as possible. Describe your preprocessing/data structure choice and implement the query interface. Constraints (for complexity goals): 1 <= N <= 10^7 Number of queries Q can be large (e.g., >= 10^5) Example: Array: [0,1,1,0,1] Query [1,4] -> 3 Query [0,0] -> 0 Provide at least 5 test cases including edge cases. Example Input A=[0,1,1,0,1] q=1 1 4 Output 3