Absolute Elements Sums

I was trying to solve this problem on Hackerrank. https://www.hackerrank.com/challenges/playing-with-numbers/problem

Given an array of integers, you must answer a number of queries. Each query consists of a single integer, x, and is performed as follows:

• Add x to each element of the array, permanently modifying it for any future queries.
• Find the absolute value of each element in the array and print the sum of the absolute values on a new line.

Can someone explain this solution to me?
I didn't quite understand the need to search for -q in the array n = bisect_left(arr, -q) and this line (Sc[-1] - 2 * Sc[n] + q * (N - 2 * n).

from bisect import bisect_left
def playingWithNumbers(arr, queries):
    N = len(arr)
    res = []

    # Calculate cummulative sum of arr
    arr = sorted(arr)
    Sc = [0]
    for x in arr:
        Sc.append(x+Sc[-1])

    q = 0
    for x in queries:
        q += x
        n = bisect_left(arr, -q)
        res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n)))
    return res

Thank you

it's actually one of the solutions from the leaderboard. I tried running this code, but didn't fully understand why they used those terms and the idea of the code

Okay, I see this now... It's a "smartass" way of calculating it. I actually thought about this idea when I read the task but I didn't thought of the specifics.

Idea is: When you add x to each element, that element's absolute value changes by at most x - drops when you add to negative/subtract from positive, rises when you add to positive/subtracts from negative.

Having a cumulative sum of a sorted list allows you to not go through the list each time and add, and sum, but to just calculate the value.

---

Let's analyse it by taking the example input from the site:

3
-1 2 -3
3
1 -2 3 

Our function gets: arr = [-1, 2, -3]; queries = [1, -2, 3]

After sorting into arr = [-3, -1, 2] (let's say those are a,b,c - letters are better at explaining why this works) we get our cumulative sum Sc = [0, -3, -4, -2] (0, a, a+b, a+b+c).

Now starts the smarty-pants part:

-q is where our values turn over in the arr - that is, where adding q would go over 0, making the absolute value rise, instead of drop

Let's translate this res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n))) one-by-one:

1. Sc[-1] is the sum (a+b+c)
2. let's take q*N first, it's how the whole sum changed when adding q (all x values up to this point) to each element
3. Let's take - 2 * Sc[n] and q * (-2*n) together: -2 * (Sc[n] + q*n) - this is the turnover point I mentioned - if we have a negative number (we looked up -q, but we add q to it), neg - 2*abs(neg) = abs(neg), we use Sc and *n to turn over all the negative values.

---

This solution's complexity is O(max(n,m)*logn) - because of the sorting. The cumulative sum thing is O(n), the smart loop is O(m*logn) (bisection is O(logn), I forgot it in the comment).

Naive method with changing the values in the list would be O(n*m) - m times going through n-length list.