1.Introduction

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_2 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.