duckladydinh's blog

Is there a simple data structure (like std::set) that allows querying on 2 parameters? (one for max/min query and the order for constraints)
By duckladydinh, history, 6 years ago, In English

[Updated] Hello everyone,

do you know if there is any data structure (like std::set) that allows querying on 2 parameters and adding elements? The use case is I have a list of (a[i], b[i]). I want perform a query with parameter MAXB that returns the pair with the maximum value by a[i] but the corresponding b[i] value is less than or equal to MAXB. I also want to perform an update by adding a pair.

Do you know any? Thank you.

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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Isn't that sorting by b and querying the maximum on a prefix (which can be precomputed)? Also you could use Binary Indexed Trees, that would lead to a 10-lines code. As for the general question I don't really get it

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah :o , I am sorry for the unclear description. I also want to add (and if possible, remove) an element from each set. I have updated the post. Thank you.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Even though it's not as easy as std::set, any augmented BBST can definitely do what you ask.

Use the b values as keys and save in each node the biggest a value in the subtree.

Adding a node is just plain insertion plus maintaining max_a for each node of the BBST. Querying is a bit more complicated, but should still be O(h). When traversing the tree, if current node's key is > MAXB, you just return query on left subtree. Otherwise, you return max between left subtree max_a and query on right sub tree.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, actually I want to avoid them, but I have found out that fenwich tree + map is the way to go, or even just map.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With the BBST approach you can easily modify it to also support query on [MINB, MAXB], so I'd recommend you to give it a go — I think both Treap and AVL trees are not particularly difficult to learn, and Treap is also quite fast to write from scratch :)

      Fenwick + map should have O(log2N) complexity per operation, you can also do the same with a "dynamic" segment tree — queries would be O(logM), unless you can solve the problem offline.

      How would you do it using only a map?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Map is similar to a set of pairs, and the method is the same as as described below by geniucos, but I think map maybe easier :)

        And basically, I know persistent Treap, or to be more precise I know only one use case from it, which is to represent a (or many) dynamic sequence that allows cut, insert, remove, add, query (min/max/sum) in O(logn), but unfortunately, I am not yet able to use it for this purpose yet :).

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In this case, persistence is not needed. I'll try to reformulate, using a[i] as BST keys instead.

          For each node of the BST, store the MINB value of the sub-tree. You will need to update this information while adding / removing nodes from the tree.

          When querying for MAXB, you move to the right sub-tree if right.MINB ≤ MAXB. If current.MINB ≤ MAXB you return current.a, otherwise you query on the left sub-tree.

          This is very similar to what you would do using a "dynamic segment tree". Also, you can extend this quite easily adding a MAXA constraint by avoiding to query on right sub-tree if current.a ≥ MAXA.

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Requests offline or online?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

It should work with set < pair < int, int > > as well: Just add pairs (b[i], a[i]). Always make sure to delete the useless pairs: a pair (b[j], a[j]) is useless if and only if there exists k so that (b[k]<=b[j] and a[k]>=a[j]) so k is always better than j and then you may as well delete j for good. In order to do so it's enough to check at each point the relationship between 2 consecutive elements of the set. When doing an insert you will first check if the element that you've just inserted is not useless (case in which you just don't add it anymore). If it is useful, then its appearance may make others useless keep checking something like while next (it) is useless delete next (it). When having only useful pairs you have the property that b1<b2<..<bp and a1<a2<..<a[p] where p is the size of the set. So using upper bound and subtracting one from it should take you to the pair with maximum b, which is also useful, and thus has maximum a. This can be coded really shortly and it's set based.

LE: the complexity will be of course O(NlogN) and online since the while acts just like the while of a stack: it deletes elements and overall we have at most N elements to delete from.

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think that any kind of balanced tree (such as splay, treap, red–black tree etc.) can solve this problem.

→ Reply