CODEWITHSUNDEEP
algorithmfenwick-tree
1110101001
1110101001

Reputation: 5097

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?

Upvotes: 1

Views: 383

Answers (1)

shebang
shebang

Reputation: 413

As an analogue for the plane problem, consider this:

  1. 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]
  2. When iterating in ascending order, all points that were considered earlier lie on the left compared to the current (i, P[i])
  3. 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:

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

Upvotes: 1

Related Questions