Simplifying $\sum\limits^n_{i=1}\bigl(\prod\limits^n_{j=1}\bigl(a_j\bigl\lfloor\frac{x_j-x_i}{|x_j-x_i|+1} \bigr\rfloor+1\bigr)\bigr)b_i$

Question

I have an indexed finite set of elements $X = \{x_1,x_2,x_3,...,x_n\}$, where $x_i \in \mathbb{R}$. And a corresponding indexed finite set $A = \{a_1,a_2,a_3,...,a_n\}$, where $a_i \in [0,1]$ and a third set $B = \{b_1,b_2,b_3,...,b_n\}$, where $b_i \in [0,1]$. And $|A| = |B| = |X| = n$.

I have spent weeks simplifying my system down to the following equation: $$F = \sum^n_{i=1}\left(\prod^n_{j=1}\left(a_j\left\lfloor \frac{x_j-x_i}{|x_j-x_i|+1} \right\rfloor + 1\right)\right)b_i$$ As you can see it has 2 nested "loops", the product inside the sum, which gives it quadratic complexity. I am going to be computing this for millions of elements in realtime and a quadratically increasing number of floor functions is a no go in terms of performance, $O(n^2)$, but I need $O(n)$.

I need to simplify the above expression into an expression without nested products or sums.

What I have tried:

1. Breaking up: $\prod\limits^n_{j=1}\left(a_j\left\lfloor \frac{x_j-x_i}{|x_j-x_i|+1} \right\rfloor + 1\right)$ into:
   a) $\prod\limits^n_{j=1}(a_j + 1) - \text{??} = \prod\limits^n_{j=1}\left(a_j\left\lfloor \frac{x_j-x_i}{|x_j-x_i|+1} \right\rfloor + 1\right)$, but I wasn't able to get a closed form for ??.
2. I have tried multiply out all of F and tried just simplifying it for 2, 3, 4 elements of $X$.
3. I tried building up to it
   a) $F_{0} = \sum^n_{i=1}\left(\prod^n_{j=1}\left\lfloor \frac{x_j-x_i}{|x_j-x_i|+1} \right\rfloor \right) = \sum^n_{i=1}\left\lfloor \frac{(\forall x_{j} \in X, min(x_j))-x_i}{|(\forall x_{j} \in X, min(x_j))-x_i|+1} \right\rfloor $
   b) $F_{1} = \sum^n_{i=1}\left(\prod^n_{j=1}a_{j}\left\lfloor \frac{x_j-x_i}{|x_j-x_i|+1} \right\rfloor \right) = (\prod^n_{j=1}a_{j})\sum^n_{i=1}\left\lfloor \frac{(\forall x_{j} \in X, min(x_j))-x_i}{|(\forall x_{j} \in X, min(x_j))-x_i|+1} \right\rfloor $

All by efforts lead to dead ends, any help would be appreciated!

Answer 1

If $X$ is guaranteed to be sorted, the complexity does can be reduced to $O(n)$, otherwise the sorting stage takes $O(n \log n)$.

The crucial part is simplifying the term $a_j \left\lfloor \dfrac{x_j - x_i}{|x_j - x_i| + 1} \right\rfloor + 1$. If $x_j \geqslant x_i$, then$$ 0 \leqslant \frac{x_j - x_i}{|x_j - x_i| + 1} < 1 \Longrightarrow a_j \left\lfloor \frac{x_j - x_i}{|x_j - x_i| + 1} \right\rfloor + 1 = 1, $$ which makes this term omissible in the product. If $x_j < x_i$, then$$ -1 < \frac{x_j - x_i}{|x_j - x_i| + 1} < 0 \Longrightarrow a_j \left\lfloor \frac{x_j - x_i}{|x_j - x_i| + 1} \right\rfloor + 1 = 1 - a_j. $$ Therefore, if $x_1 \leqslant \cdots \leqslant x_n$, then\begin{gather*} \sum_{i=1}^n b_i \prod_{j=1}^n \left( a_j \left\lfloor \frac{x_j-x_i}{|x_j-x_i|+1}\right\rfloor + 1 \right) = \sum_{i=1}^n b_i \prod_{j = 1}^{i - 1} (1- a_j)\\ = (( \cdots b_n(1 - a_{n - 1}) \cdots )(1 - a_2) + b_2)(1 - a_1) + b_1, \end{gather*} where the last line mimics the usual evaluation scheme for polynomials.