Binary grouping

Revision en10, by zhengqingyuan, 2024-09-11 09:58:53

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,we use the method on AC-Automation and solve the task easily.

Tags data structures, dynamic, implementations

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)