https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
--- Comment #12 from Xi Ruoyao <xry111 at mengyan1223 dot wang> --- Created attachment 47615 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=47615&action=edit patch optimizing pb_ds tree split, RFC I made up a patch but I doubt if this is really useful in competitive programming. (I just tried to find a problem to test the split functionality but I couldn't find one.) (1) Even with this patch, splitting with rb_tree_tag is still stupidly slow. pb_ds documentation says it is "poly-logarithmic complexity". It's too loose - maybe $O(log n)^3$? So the only useful case is with splay_tree_tag. (2) It's impossible to implement any "batch updating" with pb_ds. For example, considering a problem where we would maintain an integer set $S$, supporting several operations on it: add a: $S \leftarrow \{x \in S | x + a\}$ query b: output $\min_{x \in S} |b - x|$ rm c: remove $c$ from $S$, if $c \in S$ ins d: insert $d$ into $S$ This is a splay problem, but requiring batch updating and lazy evaluation. Unfortunately we just can't do it with pb_ds. I believe this "defect" directly makes split/join useless. Then should we add more functionality into pb_ds? I think Jonathan won't agree since he is absolutely correct that GCC is not to help people in programming contests. But if we not, pb_ds won't be very useful. Only very naive splay problems can be solved with it. In real contests my friend wang9897 can manually code a splay tree before I finish up all the tree_order_statistics_node_update stuff, for those naive problems.
