Search for maximal value smaller than V in an array composed of K linear functions
It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time.

This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays.


the subarray $A[0], A[1]$ with $C=A[1]-A[0]$.
the subarray $A[1], A[2]$ with $C=A[2]-A[1]$.
$\cdots$
the subarray $A[N-2], A[N-1]$ with $C=A[N-1]-A[N-2]$.


With $o(N)$ time preprocessing and $o(K)=o(N)$ time processing, an algorithm will not be able to even read some number in $A$ when $N$ is large enough. (In fact, most of the numbers in $A$.) So, for some queried value $q$, the algorithm will fail to recognize that $q+1$ appears in $A$. 

(The explanation above could be made more rigorous, for example, using the formal method of adversary and a well-defined model of computation.)



It looks like the more interesting question to ask should be whether there is an algorithm with $o(N\log N)$ preprocessing and $o(K)$ per query. Or whether there is algorithm with $o(N)$ preprocessing and $o(K)$ per query given $K=o(N)$. That sounds like another question, anyway.