Binary grouping
Разница между en15 и en16, 203 символ(ов) изменены
# 1.Introduction↵
Binary grouping is a way to implent dynamic insertion.If you found that 
datas can be partitioned while solvthe query for a data structure constructed by inserted elements from set $s$ can be solved by uniting querys from a set of data structures built on a partition of $S$ in $O(h(n,m))$ as m is th number of elements ing the queryspartition and you can construct a data structure in $O(\operatorname{f}(n))$,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.Then we build a data structure for each group of insertions using the construct algorithm.↵

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(\sum {f(2 ^ {a_k}) * a_k}) \approx O(f(n)\log_2 n)$ in total.↵
# 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.In the task,we use a group to deal with the inserted string and an another group for deleted strings.In both of the groups,we devide the strings into groups and deal with insertions using the method and make ACAM for each group.↵
When we insert a string,we insert it to the group of inserted strings and insert it to the group of deleted string when we delete it.For querys,if $x_i$ means that How many string is concluded if we arrive index $i$ while running the ACAM,$y_i$ is how many string ends here in the trie,we get $x_i = y_i + x_{fail_i}$,and the way to get answer is:↵

1. Run all the ACAMs in the group of inserted strings and add $x_i$ to answer while arriving index $i$.↵
2. Run all the ACAMs in the group of deleted strings and minus answer by $x_i$ while arriving index $i$.↵

Here is the [Accepted submission](https://codeforces.me/contest/710/submission/276537869).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en31 Английский zhengqingyuan 2024-09-12 11:51:36 5
en30 Английский zhengqingyuan 2024-09-12 11:50:50 3626
en29 Английский zhengqingyuan 2024-09-12 11:27:04 310
en28 Английский zhengqingyuan 2024-09-12 09:54:54 8 Tiny change: 'ho invent and use the metho' -> 'ho invent the metho'
en27 Английский zhengqingyuan 2024-09-12 09:48:14 87
en26 Английский zhengqingyuan 2024-09-12 09:46:17 1 Tiny change: '$ elementss into gro' -> '$ elements into gro'
en25 Английский zhengqingyuan 2024-09-12 09:45:02 65
en24 Английский zhengqingyuan 2024-09-12 09:42:27 49
en23 Английский 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 Английский zhengqingyuan 2024-09-12 09:40:08 60
en21 Английский 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 Английский zhengqingyuan 2024-09-12 09:36:48 228
en19 Английский zhengqingyuan 2024-09-12 09:31:15 6 Tiny change: '2 ^ {a_k}) * a_k}) \approx' -> '2 ^ {a_k})}) \approx'
en18 Английский zhengqingyuan 2024-09-12 09:30:13 23 Tiny change: 's$ can be solved' -> 's$ can be answered online and be solved'
en17 Английский 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 Английский zhengqingyuan 2024-09-12 09:28:51 203
en15 Английский 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 Английский zhengqingyuan 2024-09-12 09:21:30 76
en13 Английский zhengqingyuan 2024-09-12 09:18:31 113
en12 Английский zhengqingyuan 2024-09-11 10:50:19 950
en11 Английский 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 Английский zhengqingyuan 2024-09-11 09:58:53 345 (published)
en9 Английский zhengqingyuan 2024-09-10 11:58:54 3 Tiny change: 'e example.\\nIn [CF71' -> 'e example. \nIn [CF71'
en8 Английский zhengqingyuan 2024-09-10 11:58:46 1 Tiny change: ' example.\nIn [CF71' -> ' example.\\nIn [CF71'
en7 Английский zhengqingyuan 2024-09-10 09:00:02 278
en6 Английский zhengqingyuan 2024-09-10 08:55:32 448
en5 Английский zhengqingyuan 2024-09-10 08:44:47 131
en4 Английский zhengqingyuan 2024-09-10 08:42:33 2 Tiny change: 'mples.\n\n* 1.Binary ' -> 'mples.\n\n# 1.Binary '
en3 Английский zhengqingyuan 2024-09-10 08:42:15 2
en2 Английский zhengqingyuan 2024-09-09 12:08:08 2 Tiny change: 'mples.\n\n# 1.Binary ' -> 'mples.\n\n* 1.Binary '
en1 Английский zhengqingyuan 2024-09-09 12:04:58 450 Initial revision (saved to drafts)