Counting number of points in lower left quadrant?

I am having trouble understanding a solution to an algorithmic problem

In particular, I don't understand how or why this part of the code

s += a[i];
total += query(s);
update(s);

allows you to compute the total number of points in the lower left quadrant of each point.

Could someone please elaborate?

Solution

As an analogue for the plane problem, consider this:

For a point (a, b) to lie in the lower left quadrant of (x, y), a < x & b < y; thus, points of the form (i, P[i]) lie in the lower left quadrant of (j, P[j]) iff i < j and P[i] < P[j]
When iterating in ascending order, all points that were considered earlier lie on the left compared to the current (i, P[i])
So one only has to locate all P[j]s less that P[i] that have been considered until now

*current point refers to the point in consideration in the current iteration of the for loop that you quoted ie, (i, P[i])

Let's define another array, C[s]:

C[s] = Number of Prefix Sums of array A[1..(i - 1)] that amount to s

So the solution to #3 becomes the sum ... C[-2] + C[-1] + C[0] + C[1] + C[2] ... C[P[i] - 1], ie prefix sum of C[P[i]]

Use the BIT to store the prefix sum of C, thus defining query(s) as:

query(s) = Number of Prefix Sums of array A[1..(i - 1)] that amount to a value < s

Using these definitions, s in the given code gives you the prefix sum up to the current index i (P[i]). total builds the answer, and update simply adds P[i] to the BIT.

We have to repeat this method for all i, hence the for loop.

PS: It uses a data structure called a Binary Indexed Tree (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees) for operations. If you aren't acquainted with it, I'd recommend that you check the link.

EDIT: You are given a array S and a value X. You can split S into two disjoint subarrays such that L has all elements of S less than X, and H that has those that are greater than or equal to X.

A: All elements of L are less than all elements of H.

Any subsequence T of S will have some elements of L and some elements of H. Let's say it has p elements of L and q of H. When T is sorted to give T', all p elements of L appear before the q elements of H because of A.

Median being the central value is the value at location m = (p + q)/2

It is intuitive to think that having q >= p implies that the median lies in X, as a proof: Values in locations [1..p] in T' belong to L. Therefore for the median to be in H, it's position m should be greater than p:

m > p
(p + q)/2 > p
p + q > 2p
q > p
B: q - p > 0

To computer q - p, I replace all elements in T' with -1 if they belong to L ( < X ) and +1 if they belong to H ( >= X) T looks something like {-1, -1, -1... 1, 1, 1} It has p times -1 and q times 1. Sum of T' will now give me:

Sum = p * (-1) + q * (1)
C: Sum = q - p

I can use this information to find the value in B.

All subsequences are of the form {A[i], A[i + 2], A[i + 3] ... A[j + 1]} since they are contiguous, To compute sum of A[i] to A[j + 1], I can compute the prefix sum of A[i] with P[i] = A[1] + A[2] + .. A[i - 1] Sum of subsequence from A[i] to A[j] then can be computed as P[j] - P[i] (j is greater of j and i) With C and B in mind, we conclude:

Sum = P[j] - P[i] = q - p  (q - p > 0)
P[j] - P[i] > 0
P[j] > P[i]

j > i and P[j] > P[i] for each solution that gives you a median >= X

In summary:

Replace all A[i] with -1 if they are less than X and -1 otherwise
Computer prefix sums of A[i]
For each pair (i, P[i]), count pairs which lie to its lower left quadrant.