[Segment Tree?] Count the number of pairs in a range less than a given pair.

5 weeks ago, # ^ |

← Rev. 2 →

Usual lower_bound won't work here. Please note, my operator definition of < operator. I want both the .first and .second of pair to be less than the other.

Lower bound will just check them based on .first and if they are equal, then only check for the .second.

Example:- $$$a=[(0,0),(1,2),(2,1)]$$$

I want lower_bound({2,1}) to return 1, but instead as per your solution it will return 2.

Also, how can we use merge-Sort tree in case of pairs ? Please provide link for Task 1 is you saw it somewhere.

→ Reply

dougalves

5 weeks ago, # ^ |

← Rev. 2 →

Your definition to operator < do not allow us to do a proper sort on the array, so I think it'll be difficulty to find an efficient solution.

Ex:

[(1,2), (2,1)] is not sorted because (1,2) < (2,1) is false;
[(2,1), (1,2)] is not sorted because (2,1) < (1,2) is also false;

→ Reply

5 weeks ago, # ^ |

Yes I know that it can't be sorted normally and the closest way of visualizing it in my opinion, is a directed graph, where a new branch is created each time p1>p2 and p2>p1 both are false.

And the branches are joined by a node if some certain node is greater than end node of 2 branches. In this case (3,3) joins them.

And hence the answer will be the set of nodes which can be visited starting at that given node.

→ Reply

doraimota

5 weeks ago, # |

-16

First Task Can Also Be Solved With Divide And Conquer Algorithm Because It Involves A 3 Dimensional Inversion Counting Please Give This Comemnt Upvotes!!!!!!!!!!!!!1

→ Reply

5 weeks ago, # ^ |

Link or tutorial or some broader explanation of how to do it?

→ Reply

doraimota

5 weeks ago, # ^ |

← Rev. 2 →

-24

another example of me comment and lgm comment say same thing but only he get upvoted

→ Reply

5 weeks ago, # ^ |

As someone who never heard of a 3D Divide-and-Conquer, how am I supposed to know what that is and how to implement that?

I even googled it and found nothing. The topic might be very basic/obvious to you but the same doesn't apply to others you are explaining to. That's why I asked for a link/description to understand what you are saying.

→ Reply

5 weeks ago, # |

← Rev. 2 →

The first task is true 3D (offline) query. there is nothing better than except one of the many $$$O(n log^2 n)$$$ solutions. See https://oi-wiki.org/misc/cdq-divide/ and https://www.luogu.com.cn/problem/P3810. I hope you can read chinese.

Second task is very close to a full 3D query, I don't think it is realistic to expect anything simpler except n log^2 n.

The third task is a 2D query, simple sweepline + any choice of log DS will do in n log n .

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

Thanks a lot! Never knew about this website, before you mentioned.

For Task 2 I was wondering if we could do something like this:

Apply coordinate compression on the first element of pairs (for using them as index).
Create a mergeSort-tree initialized to $$$-\infty$$$
While iterating through the array: update(pair.first[index],pair.second[value])
Query for number of elements whose value > pair.second in the range [0,pair.first-1]

But updating and querying requires $$$O(\log^2 n)$$$ in a mergeSort-tree.

Can this be optimized to $$$O(logn)$$$? Using fractional cascading and some pre-processing maybe?

→ Reply

5 weeks ago, # ^ |

what I stated was inaccurate, in fact, your second task is exactly a 3D offline query ( given triples (i,j,k), calculate how many pairs satisfy $$$i_1 < i_2$$$, $$$j_1 > j_2$$$, $$$k_1 > k_2$$$.)

So I highly doubt there is a solution faster than $$$O(\log^2 n)$$$ on average, (given how well known this is in China).

what you described is one of the standard realistaion of a fully online 2D data structure (supporting add 2D point, and range sum query for 2D rectangle), it is highly unlikely that this can be optimised to $$$O(\log n)$$$ for this reason.

can fractional cascading be applied? defintely not directly (for reasons including it does not make sense unless it is a completely sorted array). But, I am not good enough to conclude that it is impossible, because it is possible that is some magical $$$O(n log n)$$$ solution out there (I did a quick search and it seems that this is an open problem) -- the world is waiting on anyone that can confirm or deny this.

→ Reply

5 weeks ago, # ^ |

just out of curiosity what do you mean by 2D , 3D stuff ? why did u call sweepline 2D ?

→ Reply

5 weeks ago, # ^ |

← Rev. 3 →

the general DS/solution to a k-dimensinoal query is $$$O(n log^k n)$$$.

In the special case that our queries are offline, then we can reduce dimension by one, using sort+ sweepline and use an online solution for it. So an offline 2D query = sweepline plus any online 1D structure is $$$O(n \log n)$$$. The general 2D data structures, including BBST (ordered set) on segment tree, or 2DBIT, supporting online queries, are all $$$O(n \log^2 n$$$).

Wavelet tree, persistent segment tree or merge sort tree (with fractional cascading) are special cases (all $$$O(n \log n)$$$.) that can handle queries (l,r,v): count how many A[i] >= v for i in [l,r] if there are no update queries, (so, partially offline). This is weaker than the general full 2D online queries.

→ Reply

5 weeks ago, # ^ |

oh i see , this generalizes stuff and makes it alot easier

→ Reply

5 weeks ago, # ^ |

could u give a general idea on how to solve any k dimensional query in nlog^kn online ?

like given a 4D query how would u do it in nlog^4n ? make a segment inside a segment inside a segment 3 times ? or how would u generalize a solution to any k dimensional query ?

→ Reply

5 weeks ago, # ^ |

+11

Yes, nesting (implicit) segment trees seems to be the best option.

The final one could be a BBST to save memory, giving a memory requirement of $$$O(n log^{k-1} n)$$$.

If the overall set-up is offline, generally, you can use one extra layer of cdq to remove one dimension ( so still $$$O(n log^k n)$$$ but easier to code and better constant factor).

Of course, it is unlikely that you get anything practically better than the $$$O(n^2)$$$ for 5 dimensions or higher (4 dimensions already questionable).

→ Reply