How to make dynamic insertions of some Data structures availableBinary grouping
Difference between en9 and en10, changed 345 character(s)
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↵
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)$.↵
## 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](https://codeforces.me/contest/710/problem/F),we use the method on AC-Automation and solve the task easily.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en31 English zhengqingyuan 2024-09-12 11:51:36 5
en30 English zhengqingyuan 2024-09-12 11:50:50 3626
en29 English zhengqingyuan 2024-09-12 11:27:04 310
en28 English zhengqingyuan 2024-09-12 09:54:54 8 Tiny change: 'ho invent and use the metho' -> 'ho invent the metho'
en27 English zhengqingyuan 2024-09-12 09:48:14 87
en26 English zhengqingyuan 2024-09-12 09:46:17 1 Tiny change: '$ elementss into gro' -> '$ elements into gro'
en25 English zhengqingyuan 2024-09-12 09:45:02 65
en24 English zhengqingyuan 2024-09-12 09:42:27 49
en23 English zhengqingyuan 2024-09-12 09:40:26 2 Tiny change: 'al and $O(g(n,\log_2 ' -> 'al and $O(h(n,\log_2 '
en22 English zhengqingyuan 2024-09-12 09:40:08 60
en21 English zhengqingyuan 2024-09-12 09:38:33 29 Tiny change: 'O(\sum {f(2 ^ {a_k})}) \approx ' -> 'O(\sum {f(x)})(\sum x = n \log_2 n) \approx '
en20 English zhengqingyuan 2024-09-12 09:36:48 228
en19 English zhengqingyuan 2024-09-12 09:31:15 6 Tiny change: '2 ^ {a_k}) * a_k}) \approx' -> '2 ^ {a_k})}) \approx'
en18 English zhengqingyuan 2024-09-12 09:30:13 23 Tiny change: 's$ can be solved' -> 's$ can be answered online and be solved'
en17 English zhengqingyuan 2024-09-12 09:29:23 3 Tiny change: 'n,m))$ as m is th number of' -> 'n,m))$ as $m$ is the number of'
en16 English zhengqingyuan 2024-09-12 09:28:51 203
en15 English zhengqingyuan 2024-09-12 09:21:47 2 Tiny change: '2 ^ {a_k})) * a_k} \approx O' -> '2 ^ {a_k}) * a_k}) \approx O'
en14 English zhengqingyuan 2024-09-12 09:21:30 76
en13 English zhengqingyuan 2024-09-12 09:18:31 113
en12 English zhengqingyuan 2024-09-11 10:50:19 950
en11 English zhengqingyuan 2024-09-11 09:59:49 2 Tiny change: 's $O(T\log n)$ in to' -> 's $O(T\log_2 n)$ in to'
en10 English zhengqingyuan 2024-09-11 09:58:53 345 (published)
en9 English zhengqingyuan 2024-09-10 11:58:54 3 Tiny change: 'e example.\\nIn [CF71' -> 'e example. \nIn [CF71'
en8 English zhengqingyuan 2024-09-10 11:58:46 1 Tiny change: ' example.\nIn [CF71' -> ' example.\\nIn [CF71'
en7 English zhengqingyuan 2024-09-10 09:00:02 278
en6 English zhengqingyuan 2024-09-10 08:55:32 448
en5 English zhengqingyuan 2024-09-10 08:44:47 131
en4 English zhengqingyuan 2024-09-10 08:42:33 2 Tiny change: 'mples.\n\n* 1.Binary ' -> 'mples.\n\n# 1.Binary '
en3 English zhengqingyuan 2024-09-10 08:42:15 2
en2 English zhengqingyuan 2024-09-09 12:08:08 2 Tiny change: 'mples.\n\n# 1.Binary ' -> 'mples.\n\n* 1.Binary '
en1 English zhengqingyuan 2024-09-09 12:04:58 450 Initial revision (saved to drafts)