Application of binary indexed tree

Question

I was trying to solve this algorithmic problem and I came across this nice solution:

"The idea is to treat the a_i, b_i and c_i asymmetrically. The BIT supports minimum queries for key intervals starting at 1. We use c_i as values and b_i as keys. Those are inserted in the order of increasing a_i. This way, for each a_i in turn, the data structure allows queries for the smallest value of c_j (possibly ∞) for b_j in [1..b_i) and a_j < a_i. We have c_j < c_i if and only if contestant i is not excellent."

source

Now I am having hard time understanding this solution.

Here's what I understand of this solution: I know that binary indexed tree is used to answers queries like finding sum of an interval in an array and it also support updates in elements. It does both the operations in O(logn) time complexity each. Now this solution says that we build BIT with keys as c_i, and value as b_i, that is basically b_i is an additional value that goes with each node. Now we insert elements in the tree with increasing values of a_i, this is where I lost the grip. How does it matter in what order we are inserting nodes and what the statement says following that part, I have no idea.

Please help me understand what this solution says.

Answer 1

Let's find all non-excellent participants. Another participant j can be better than the participant i only if his a[j] < a[i]. Thus, we can ignore all participants with a larger value of a[j]. That's why we sort them by a.

This condition is necessary, but it's not sufficient. We also need to check b and c. How can we do that? We need to know if there's a guy a[j] < a[i] (that is, the one who goes before the current one in the sorted order) such that his b[j] < b[i] and c[j] < c[i]. We build a BIT (with c[j] as keys and b[j] is values) to check the last two conditions. It's clear that such j exists if and only if the minimum on the prefix [0, c[i]) is less than b[i].

To sum up, the idea is as follows: we sort them by a[i] and then ignore the values of a. This way, we go from a 3-D to a 2-D problem, which is simpler to solve (that's why the order matters. The guy with larger a[i] is never better). We use a BIT to solve a 2-D problem.