How would we implement a multiset data structure that allows insertion, deletion and querying GCD of values currently present in multiset?
insert(5) GCD() -> 5 insert(10) GCD() -> 5 remove(5) GCD() -> 10
This question is not from some existing problem and was just wondering if it was possible to have such data structure where deletion is possible on operations like GCD. I believe this would be helpful https://cp-algorithms.com/data_structures/deleting_in_log_n.html but can't understand how we would apply this or maybe some other method which would work for large numbers upto 1e18.
Treaps. Just modify the "upd_cnt()" function to merge GCD values of the subtrees.
you can use dynamic segment tree, which support these operation in O(log n) (Although GCD is O(log n), but realistically, it is much faster than that, so we assume it is O(1))
Splay also works here.
No need to use a dynamic tree, just use a large enough fixed size segment tree with GCD as the operation and a map to track where in the segtree your elements are.