Search code examples
algorithminterval-treebinary-indexed-tree

Can someone please explain the solution to "Almost sorted intervals" to me?

Here is the problem, and here is a solution.

First part is simple enough. It's the second part that I don't get, no matter how hard I try. You basically have two sets of intervals and need to find all intersections where one interval is not completely inside another.

I have been staring at problem setter code until my eyes started to bleed. Still cannot understand this bit:

for(int L=n;L>=1;L--) {
   FOR(it, r[L]) add(*it, -1);
   add(L, 1);
   r[left[L]].push_back(L);
   ans += ask(right[L]-1);
}

How does it work? What's the algorithm?

It is noted in the editorial that you can solve this using interval tree or "Binary Indexed Tree". I understand more or less what an Interval tree is and how it can be useful. But the problem setter obviously does not use that, and "Binary Indexed Tree" does not show up in search, instead there is "Binary Indexed Tree", which deals with partial sums and I fail to see how it is relevant (it may very well be that it is relevant, but I don't understand how).

Any help? Pointers to literature I need to read?

Solution

  • OK, got it. It's a binary indexed tree - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees. And yes, it is relevant.