Thrb_73's blog

Is there an (O(n \log n)) solution without PBDS / Ordered Set?
By Thrb_73, history, 2 months ago, In English

I was solving a problem where we have k intervals, and we need to count the number of nested pairs.

More formally, count pairs (i, j) such that:

l_i < l_j <= r_j < r_i

(or equivalently after sorting by the left endpoint, count previous intervals whose right endpoint is greater than or equal to the current one).

The standard solution is:

  1. Sort intervals by the left endpoint.
  2. Insert right endpoints into an ordered_set (PBDS).
  3. Use order_of_key() to count how many previous right endpoints are greater than or equal to the current one.

This gives an O(n log n) solution.

My question is:

Is there an O(n log n) or O(n) solution that does not use PBDS (ordered_set), GNU extensions, or similar policy-based data structures?

I'm looking for alternatives using only standard C++ (STL). Thanks!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Thrb_73 (previous revision, new revision, compare).

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Segment trees or Binary search trees can do that in O(nlogn).

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks for your answer!

    I was actually looking for a solution that doesn't rely on advanced data structures like Segment Trees, Fenwick Trees, or balanced BSTs/PBDS.

    I was wondering if there's a simpler algorithm using only basic STL containers and techniques, or if such a solution simply doesn't exist.

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Suffix-sum can also do this.

      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Thanks! Could you explain that approach a bit more?

        I'm not sure how suffix sums can be used here after sorting the intervals. A brief explanation or pseudocode would be really helpful.

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          You need to discrete all the l and r.

          And update the suffix sum

          Wait my solution was wrong it can up to $$$O(n^2)$$$

          Maybe you can use a Fenwick Tree.

          → Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Observe that any two segments can be either completely separate, partially overlapping (including sharing a border), or nested. For each segment $$$i$$$ only consider those that start strictly before it ends. Then the number of nested segments is those that end strictly before $$$r_i$$$ minus those that end strictly before $$$l_i$$$ and those that start before or at $$$l_i$$$ and end strictly before $$$r_i$$$.

  1. Do coordinate compression so $$$l_i,r_i\le 2n$$$. This takes $$$O(n\log n)$$$ time.

  2. For each $$$l$$$ and $$$r$$$ value, make a vector of the segments that start and end here, respectively. Call those $$$s_i$$$ and $$$t_i$$$ respectively.

  3. Iterate $$$i$$$ over the values from left to right while maintaining a running count of how many open segments there are and how many closed segments there are (both initially 0).

  4. At each value perform the following:

a. Store the open and closed running counts in $$$o_i$$$ and $$$c_i$$$, respectively.

b. Iterate $$$j$$$ through $$$t_i$$$ and add $$$c_{r_j}-c_{l_j}-o_{l_j}$$$ to the final answer.

c. Update the running counts by adding $$$|t_i|$$$ to the closed count and adding $$$|s_i|-|t_i|$$$ to the open count.

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thank you! That makes sense now. I really appreciate your detailed explanation.

    → Reply