Number of elements with lower index equal to some element, for all items on an array
Do a linear scan over the array, and use a hashtable.  Each time you see an element, add it to the hashtable (with a count of 1) if it's not already present, or increment the count of the item in the hashtable if it is already present.  As you see each element $a_r$, you can compute $f(0,r,a_r)$ by looking up $a_r$ in the hashtable and finding its count, and then record this value of $f$.  This will lead to an expected running time of $O(n)$ if you use a suitable hash function.

If you want deterministic running time, use a balanced search tree instead of a hashtable; that will achieve $O(n \log n)$ worst-case running time.