algorithm - Query min value at x of many equations in the form |x-a| + b

Question

Kind of unrelated to what I was doing, but I stumbled on this interesting data structure. I can't figure out a few details.

Suppose I have like N<10^5 equations in the form y = |x-a| + b, with 0 < x, a, b < 10^5. After O(N) preprocessing, for any x, I want to find the minimum value out of all these equations in constant time.

Here's what I have so far: add the functions one by one in increasing values of a, somehow find the intersection between the new function and the min existing function, then store intersections. The intersections can tell us what equation to use for the min. Then we can use binary search for log time queries, but since x<10^5, we can just go through all values and precompute the correct min value for each x

Visualization, where the black is the min values

question from:https://stackoverflow.com/questions/65855935/query-min-value-at-x-of-many-equations-in-the-form-x-a-b

Answer 1

The basic property of modulus is

1. |x| = x if x>=0
2. |x| = -x if x<0

Using this, the equation y = |x-a|+b can be written as

1. y = x + (b-a) if x >= a
2. y = (b+a) - x if x<a

Since b and a are constants, we can use pre-computation to get answers per query in constant time.
For a given x, there are two cases:

1. The minima lies to the left of x (i.e. a < x). If we know the minimum value of b-a for all lines with a < x, we can get the answer in O(1) time.
2. Similarly, when the minima lies on the right of x (i.e. a >= x), if we know the minimum value of b+a for all lines with a >= x, we can get the answer in O(1) time.

To summarise, we need to know the minimum value of b-a for all a on the left of x and the minimum value of b+a for all a on the right of x. This can easily be done using a simple prefix and/or suffix array implementation.