# Data structures to store monotone functions

I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $$[0..N]$$:

$$\forall x \in X: 0 \le x \le N\\ f: X \to \mathbb N\\ \forall x,y\in X:\quad x< y \Rightarrow f(x) With the goal to optimize disk footprint and, preferably, with $$O(1)$$ random access time. In my particular case, these functions are almost affine or "piecewise almost affine", if that's any help.

What would be the correct keywords that I could use to find such algorithms? Is there a book/article with an overview of existing approaches?

edit

There was a question in comments (now deleted) on what is "almost affine". By this expression I mean that there exists an affine function $$g$$ on $$X$$ such that $$D = \sup_{x\in X} |f(x) - g(x)|$$ is "small"; we can suppose for now $$D < 256$$.

• Can you clarify what you mean by "almost affine"? You mention disk footprint - how is the input f represented? Is f represented as a list of |X| values, i.e. you're looking for some compression method? Or is f represented by its "almost affine" pieces, i.e. you're looking for a searching method? Jun 9, 2022 at 6:36
• @MathiasRav Thanks for relevant questions! 1) "Almost affine" - already answered in an edit; 2) looking for a compression method, with (in Haskell notation) "fast", preferably O(1) lookup :: Word32 -> Maybe Word64 The input to build such a structure would be a list of pairs (key, value), with ascending keys. Jun 15, 2022 at 15:45