Level sums, displacements: how to determine them efficiently?

Question

Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$, $\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.

Define $$S(\delta,m) = \sum_{n\in R: \rho(n)\geq \delta} f(n+m).$$

Is it possible to compute $S(\delta,m)$ efficiently? To be precise: say we are given $\delta_i\in \lbrack 0,1\rbrack$, $m_i\in R$ for $1\leq i\leq N$. Is it possible to compute $S(\delta_i,m_i)$ for all $1\leq i\leq N$ in roughly linear time on $N$ (or some other time substantially smaller than $N^2$)?

To see why this might not be an unreasonable request, consider the two following extreme cases.

If all $m_i=0$ (or all $m_i$ are equal), we can compute the $N$ sums $S(\delta_i,m_i)$ easily in linear time.

If all $\delta_i=0$ (or all $\delta_i$ are equal), we can compute the $N$ sums $S(\delta_i,m_i)$ in roughly linear time (more precisely: $O(N \log N)$) using FFT. The reason is that $S(\delta,m_i)$ equals $F(m_i)$, where $F$ is the convolution of $f$ with the function $g(n) = \begin{cases} 1 &\text{if $\rho(-m)>\delta$,}\\ 0 &\text{otherwise.}\end{cases}$.

Is the general problem feasible? Can it be shown not to be feasible?

Answer 1

Define $$L := [(p(i),i) : i \in [1..N]]$$ and sort this list with respect to $p(i)$, this takes $O(N\log N)$.
Define $$R := [(\delta_i,i) : i \in [1..N]]$$ and reverse-sort it with respect to $\delta_i$ (biggest first), also takes $O(N\log N)$.
Now, having these lists sorted, you can run over them both and add stuff. You add the first few elements of $L$ together, until things get smaller than the first $\delta$ in $R$. Then you add to that everything until things get smaller than the second $\delta$ in $R$, etc. So all the adding takes about $O(N)$, because you don't start new for every new $i$ but only add to what you already have, giving us a total time of $O(N\log N)$.