For some Data structures,dynamic insertions might not be available if you use a simple function to build it.But as a matter of fact, using some skills based on the function to rebuild can make dynamic insertions of some Data structures available Here are some examples.

1.Binary grouping

1.Introduction

If you found that a naive algorithm to solve the query based on elements independently,It means that you can make the insertions in groups,for $$$n = \sum 2 ^ {a_i}(a_i > a_{i + 1})$$$,We can make $$$n$$$ insertions into groups,each group has $$$2^{a_k}$$$ insertions,in this way we divided insertions to $$$\log_2{n}$$$ groups.

When we insert a new insetion,we divide it in a group,and when we found a group that its size is the same as the new group,we merge the two groups into one group and rebuild a data structure with the insertions in the group.Using the method,we get a way to implent dynamic insertion and the method is $$$O(T\log n)$$$ in total if the rebuild function is $$$O(T)$$$.

2.Examples

It can be used for kd-tree,but I haven't found an example on the site,so please leave a comment if you found the example.\ In CF710F,we use the method on AC-Automation and solve the task easily.