Is it possible to calculate the average between n numbers in a static random access array of some size in less than $O(n)$ time? I know that the trivial approach is $O(n)$, but can I do it in less time using a data structure or a certain preparation? or both? I am asking for hints, not a solution.
Note: The array is of some length. What and I mean by between is when given 2 indexes a and b, I have to calculate the average of the sub array $[a+1,b-1]$. And I have to keep it updated while the data structure is managed, that's why I said it was a dynamic set, in other words a random access array. I do not know of any restrictions, just asking if it's possible in less than $O(n)$.