# 1.Introduction↵
Binary grouping is a way to implent dynamic insertion.If you found that the query for a data structure constructed by inserted elements from set $s$ can be answered online and 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 the number of subsets in the partition and you can construct a data structure in $O(\operatorname{f}(n))$,It means that you can divide the elements in groups,for $n = \sum 2 ^ {a_i}(a_i > a_{i + 1})$,We can divide $n$ elements into groups,each group has $2^{a_k}$ elements,in this way we divided elements 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 element,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 elements in the group.Using the method,we get a way to implent dynamic insertion and the method to construct is $O(\sum {f(x)})(\sum x = n \log_2 n) \approx O(f(n)\log_2 n)$ in total and $O(h(n,\log_2 n))$ for each query.↵
# 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.↵
↵
The example of using the method on kd-tree is [P4148 on luogu](https://www.luogu.com.cn/problem/P4148),in the problem,the elements is the points in the first operation and we can use kd-tree to deal with the elements and answer the query online.But we have to implent dynamic insertion,so we use this method.↵
↵
<spoiler summary="code">↵
`↵
#include<algorithm>↵
#include<cstdio>↵
using namespace std;↵
namespace K_D_tree{↵
const int N = 300009,K = 2;↵
int V = 0;↵
struct node{↵
int p[K],mx[K],mn[K],lc,rc,sz,sum,val;↵
}a[N];↵
int sro;↵
int build(int l,int r,int nk,node a[]){↵
if(l > r)↵
return 0;↵
if(l == r){↵
for(int i = 0; i < K; i ++){↵
a[l].mx[i] = a[l].p[i];↵
a[l].mn[i] = a[l].p[i];↵
}↵
a[l].sz = 1;↵
a[l].sum = a[l].val;↵
return l;↵
}↵
int m = (l + r) >> 1;↵
sro = nk;↵
nth_element(a + l,a + m,a + r + 1,[](node x,node y){return x.p[sro] < y.p[sro];});↵
a[m].lc = build(l,m - 1,(nk + 1) % K,a);↵
a[m].rc = build(m + 1,r,(nk + 1) % K,a);↵
for(int i = 0; i < K; i ++){↵
a[m].mx[i] = max(a[m].p[i],max(a[a[m].lc].mx[i],a[a[m].rc].mx[i]));↵
a[m].mn[i] = min(a[m].p[i],min(a[a[m].lc].mn[i],a[a[m].rc].mn[i]));↵
}↵
a[m].sz = r - l + 1;↵
a[m].sum = a[a[m].lc].sum + a[a[m].rc].sum + a[m].val;↵
return m;↵
}↵
int fnd(int k,int q[]){↵
if(k == 0)↵
return 0;↵
for(int i = 0; i < K; i ++){↵
if(q[i] > a[k].mx[i] || q[i] < a[k].mn[i])↵
return 0;↵
}↵
bool flg = true;↵
for(int i = 0; i < K; i ++){↵
if(q[i] != a[k].p[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg)↵
return k;↵
else ↵
return max(fnd(a[k].lc,q),fnd(a[k].rc,q));↵
}↵
void change(int k,int q[],int ad){↵
if(k == 0)↵
return ;↵
for(int i = 0; i < K; i ++){↵
if(q[i] > a[k].mx[i] || q[i] < a[k].mn[i])↵
return ;↵
}↵
bool flg = true;↵
for(int i = 0; i < K; i ++){↵
if(q[i] != a[k].p[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg){↵
a[k].val += ad;↵
a[k].sum += ad;↵
return;↵
}↵
else {↵
change(a[k].lc,q,ad),change(a[k].rc,q,ad);↵
a[k].sum = a[a[k].lc].sum + a[a[k].rc].sum + a[k].val;↵
}↵
}↵
int query(int k,int l[],int r[]){↵
if(k == 0)↵
return 0;↵
for(int i = 0; i < K; i ++){↵
if(l[i] > a[k].mx[i] || r[i] < a[k].mn[i])↵
return 0;↵
}↵
bool flg = true;↵
int ret = 0;↵
for(int i = 0; i < K; i ++){↵
if(l[i] > a[k].p[i] || r[i] < a[k].p[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg)↵
ret += a[k].val;↵
flg = true;↵
for(int i = 0; i < K; i ++){↵
if(l[i] > a[k].mn[i] || r[i] < a[k].mx[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg)↵
return a[k].sum;↵
else ↵
return ret + query(a[k].lc,l,r) + query(a[k].rc,l,r);↵
}↵
int str[100009],top = 0,lf[100009],rt[100009];↵
};↵
using namespace K_D_tree;↵
int lans,c,o,lp[K],rp[K];↵
int main(){↵
scanf("%*d");↵
while(true){↵
scanf("%d",&o);↵
if(o == 1){↵
scanf("%d %d %d",&lp[0],&lp[1],&c);↵
lp[0] ^= lans;↵
lp[1] ^= lans;↵
c ^= lans;↵
bool flg = false;↵
for(int j = 1; j <= top; j ++){↵
if(fnd(str[j],lp) != 0){↵
change(str[j],lp,c);↵
flg = true;↵
break;↵
}↵
}↵
if(!flg){↵
V ++;↵
for(int j = 0; j < K; j ++){↵
a[V].mx[j] = a[V].mn[j] = a[V].p[j] = lp[j];↵
}↵
a[V].sum = a[V].val = c;↵
a[V].sz = 1;↵
int u = 1,nlf = V;↵
while(a[str[top]].sz == u){↵
//printf("%d\n",top);↵
nlf = lf[top];↵
u = (u << 1);↵
top --;↵
}↵
top ++;↵
str[top] = build(nlf,V,0,a);↵
lf[top] = nlf;↵
}↵
}↵
else if(o == 2){↵
scanf("%d %d %d %d",&lp[0],&lp[1],&rp[0],&rp[1]);↵
lp[0] ^= lans;↵
lp[1] ^= lans;↵
rp[0] ^= lans;↵
rp[1] ^= lans;↵
//printf("%d %d %d %d\n",lp[0],lp[1],rp[0],rp[1]);↵
lans = 0;↵
for(int j = 1; j <= top; j ++){↵
lans += query(str[j],lp,rp);↵
}↵
printf("%d\n",lans);↵
}↵
else{↵
break;↵
}↵
}↵
return 0;↵
}↵
`↵
...↵
</spoiler>↵
↵
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).↵
↵
# written at the end of the blog↵
We would like to thank:↵
↵
1. Masters who invent the method;↵
2. [user:zhengqingyuan,2024-09-12] edit the blog;↵
3. [user:unalive,2024-09-12] to give advice and make the blog better.↵
4. [user:adamant,2024-09-12] suggest a good problem as an example of using the trick.
Binary grouping is a way to implent dynamic insertion.If you found that the query for a data structure constructed by inserted elements from set $s$ can be answered online and 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 the number of subsets in the partition and you can construct a data structure in $O(\operatorname{f}(n))$,It means that you can divide the elements in groups,for $n = \sum 2 ^ {a_i}(a_i > a_{i + 1})$,We can divide $n$ elements into groups,each group has $2^{a_k}$ elements,in this way we divided elements 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 element,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 elements in the group.Using the method,we get a way to implent dynamic insertion and the method to construct is $O(\sum {f(x)})(\sum x = n \log_2 n) \approx O(f(n)\log_2 n)$ in total and $O(h(n,\log_2 n))$ for each query.↵
# 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.↵
↵
The example of using the method on kd-tree is [P4148 on luogu](https://www.luogu.com.cn/problem/P4148),in the problem,the elements is the points in the first operation and we can use kd-tree to deal with the elements and answer the query online.But we have to implent dynamic insertion,so we use this method.↵
↵
<spoiler summary="code">↵
`↵
#include<algorithm>↵
#include<cstdio>↵
using namespace std;↵
namespace K_D_tree{↵
const int N = 300009,K = 2;↵
int V = 0;↵
struct node{↵
int p[K],mx[K],mn[K],lc,rc,sz,sum,val;↵
}a[N];↵
int sro;↵
int build(int l,int r,int nk,node a[]){↵
if(l > r)↵
return 0;↵
if(l == r){↵
for(int i = 0; i < K; i ++){↵
a[l].mx[i] = a[l].p[i];↵
a[l].mn[i] = a[l].p[i];↵
}↵
a[l].sz = 1;↵
a[l].sum = a[l].val;↵
return l;↵
}↵
int m = (l + r) >> 1;↵
sro = nk;↵
nth_element(a + l,a + m,a + r + 1,[](node x,node y){return x.p[sro] < y.p[sro];});↵
a[m].lc = build(l,m - 1,(nk + 1) % K,a);↵
a[m].rc = build(m + 1,r,(nk + 1) % K,a);↵
for(int i = 0; i < K; i ++){↵
a[m].mx[i] = max(a[m].p[i],max(a[a[m].lc].mx[i],a[a[m].rc].mx[i]));↵
a[m].mn[i] = min(a[m].p[i],min(a[a[m].lc].mn[i],a[a[m].rc].mn[i]));↵
}↵
a[m].sz = r - l + 1;↵
a[m].sum = a[a[m].lc].sum + a[a[m].rc].sum + a[m].val;↵
return m;↵
}↵
int fnd(int k,int q[]){↵
if(k == 0)↵
return 0;↵
for(int i = 0; i < K; i ++){↵
if(q[i] > a[k].mx[i] || q[i] < a[k].mn[i])↵
return 0;↵
}↵
bool flg = true;↵
for(int i = 0; i < K; i ++){↵
if(q[i] != a[k].p[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg)↵
return k;↵
else ↵
return max(fnd(a[k].lc,q),fnd(a[k].rc,q));↵
}↵
void change(int k,int q[],int ad){↵
if(k == 0)↵
return ;↵
for(int i = 0; i < K; i ++){↵
if(q[i] > a[k].mx[i] || q[i] < a[k].mn[i])↵
return ;↵
}↵
bool flg = true;↵
for(int i = 0; i < K; i ++){↵
if(q[i] != a[k].p[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg){↵
a[k].val += ad;↵
a[k].sum += ad;↵
return;↵
}↵
else {↵
change(a[k].lc,q,ad),change(a[k].rc,q,ad);↵
a[k].sum = a[a[k].lc].sum + a[a[k].rc].sum + a[k].val;↵
}↵
}↵
int query(int k,int l[],int r[]){↵
if(k == 0)↵
return 0;↵
for(int i = 0; i < K; i ++){↵
if(l[i] > a[k].mx[i] || r[i] < a[k].mn[i])↵
return 0;↵
}↵
bool flg = true;↵
int ret = 0;↵
for(int i = 0; i < K; i ++){↵
if(l[i] > a[k].p[i] || r[i] < a[k].p[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg)↵
ret += a[k].val;↵
flg = true;↵
for(int i = 0; i < K; i ++){↵
if(l[i] > a[k].mn[i] || r[i] < a[k].mx[i]){↵
flg = false;↵
break;↵
}↵
}↵
if(flg)↵
return a[k].sum;↵
else ↵
return ret + query(a[k].lc,l,r) + query(a[k].rc,l,r);↵
}↵
int str[100009],top = 0,lf[100009],rt[100009];↵
};↵
using namespace K_D_tree;↵
int lans,c,o,lp[K],rp[K];↵
int main(){↵
scanf("%*d");↵
while(true){↵
scanf("%d",&o);↵
if(o == 1){↵
scanf("%d %d %d",&lp[0],&lp[1],&c);↵
lp[0] ^= lans;↵
lp[1] ^= lans;↵
c ^= lans;↵
bool flg = false;↵
for(int j = 1; j <= top; j ++){↵
if(fnd(str[j],lp) != 0){↵
change(str[j],lp,c);↵
flg = true;↵
break;↵
}↵
}↵
if(!flg){↵
V ++;↵
for(int j = 0; j < K; j ++){↵
a[V].mx[j] = a[V].mn[j] = a[V].p[j] = lp[j];↵
}↵
a[V].sum = a[V].val = c;↵
a[V].sz = 1;↵
int u = 1,nlf = V;↵
while(a[str[top]].sz == u){↵
//printf("%d\n",top);↵
nlf = lf[top];↵
u = (u << 1);↵
top --;↵
}↵
top ++;↵
str[top] = build(nlf,V,0,a);↵
lf[top] = nlf;↵
}↵
}↵
else if(o == 2){↵
scanf("%d %d %d %d",&lp[0],&lp[1],&rp[0],&rp[1]);↵
lp[0] ^= lans;↵
lp[1] ^= lans;↵
rp[0] ^= lans;↵
rp[1] ^= lans;↵
//printf("%d %d %d %d\n",lp[0],lp[1],rp[0],rp[1]);↵
lans = 0;↵
for(int j = 1; j <= top; j ++){↵
lans += query(str[j],lp,rp);↵
}↵
printf("%d\n",lans);↵
}↵
else{↵
break;↵
}↵
}↵
return 0;↵
}↵
`↵
...↵
</spoiler>↵
↵
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).↵
↵
# written at the end of the blog↵
We would like to thank:↵
↵
1. Masters who invent the method;↵
2. [user:zhengqingyuan,2024-09-12] edit the blog;↵
3. [user:unalive,2024-09-12] to give advice and make the blog better.↵
4. [user:adamant,2024-09-12] suggest a good problem as an example of using the trick.
