Maximum Distance

Let's denote prefix sum as ${P_i = a_1 + a_2 + \dots + a_i}$ and suffix sum as ${S_i = a_i + a_{i+1} + \dots + a_n}$.

Now elaborate the given operation.

$| \sum\limits_{i = l}^{k} a_i - \sum\limits_{j = p}^{r} a_j |$

${ = |(a_{l} + a_{l+1} + \dots + a_{k}) - (a_{p} + a_{p+1} + \dots + a_{r})|}$

${ = |\{(a_1 + a_2 + \dots + a_k) - (a_1 + a_2 + \dots + a_{l-1})\} - \{(a_{p} + a_{p+1} + \dots + a_{n}) - (a_{r+1} + a_{r+2} + \dots + a_n)\}|}$

${ = |(P_k - P_{l-1}) - (S_p - S_{r+1})|}$

${ = |(P_k - S_p) - (P_{l-1} - S_{r+1})|}$

Here, as $P_{l-1}$ and $S_{r+1}$ are constant, the difference depends on $P_k$ and $S_p$.

Mathematically, ${|P_k - S_p| = max(P_k - S_p, S_p - P_k)}$. So, the maximum difference can be found in two cases.

1. ${P_k - S_p}$ where $P_k$ is maximum prefix sum and $S_p$ is minimum suffix sum.

2. ${S_p - P_k}$ where $S_p$ is maximum suffix sum and $P_k$ is minimum prefix sum.

So, take the maximum and the minimum prefix sum and suffix sum in the range $[l, r]$ and check which one gives the maximum difference.

Now, how can you find the maximum and the minimum prefix sum and suffix sum in the range $[l, r]$?

The answer is Segment Tree. Build a segment tree to find the maximum and the minimum prefix sum. And build another segment tree to find the maximum and the minimum suffix sum. Note that, in the segment trees, you have to keep the indices not the value. Complexity will be ${O(q \times log n)}$per testcase.