f-Arrays for Noobs.
This post is about the $f$-array data structure, which was introduced by Prasad Jayanti in f-arrays: implementation and applications (PODC 2002). What is it? An $f$-array is a data structure that can be thought of as similar to a regular array, except it provides a read() operation. This read operation returns the value of some function $f$ applied to the whole array. Furthermore, the types of the elements in the array need not be the same, so a mental model I have for the array is something like the following: ...