↵
# 1.Binary grouping↵
#
Binary grouping is a way to implent dynamic insertion.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)$.↵
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](https://codeforces.net/contest/710/problem/F),we use the method on AC-Automation and solve the task easily.
