Update：2025.5.25
Tree-shaped arrays are based on the idea of binary division and multiplication, while line segment trees are based on the idea of division and governance. The reason why it can be efficiently modified and queried is to divide the sequence into "segments" of large and small sizes, and record and update the information managed by these "segments" at the cost of additional (adding space, changing space for time), and query the information of an interval. Information, this interval can be divided into several existing "segments" to improve efficiency.
Tree-shaped arrays and line segment trees also have disadvantages, and it is difficult to maintain some information that does not meet the interval additive and subtractability., the code is not intuitive, and requires in-depth understanding and attention to many details.
When the maintained information does not meet interval merging, e.g.Interval modeTo improve efficiency, we need to block the sequence. The basic idea of blocking is "Large section of maintenance, local violence”, preprocess some information and save it, exchange space for time, and divide it into piecesMore general and easy to implement。
Classic examples:
Example 1:Getting started with serial blocks 1
Question meaning: Give a sequence of length $n(1 \le n\le 50000)$, as well as $n$ operations, operations involve interval addition and single-point search value.
Analysis: It can be solved by using tree arrays and segment trees at $O(N\log{N})$ time. Now we use chunking to solve this problem.
First, let’s set the block length as $L$, and the number of blocks is $t=\left \lceil n/L \right \rceil \approx n/L $. For any interval $(l,r)$, the entire segment within the interval only needs to modify its $lazy$ tag array, and simple modifications are made to the part that has insufficient entire segment at the beginning and end. The complexity of a single interval modification can be expressed as $ O(L+t)$, then according to the properties of the inequality:
$$L+t=L+n/L \ge 2 \times \sqrt{L*(n/L)}=2\sqrt{n}$$
When $L=n/L$, the inequality equal sign holds, that is, $L=\sqrt{n}$.
The modification complexity of $n$ is $O(n\sqrt{n})$, and the single-point inquiry complexity of $O(1)$.
Reference code:Click
Example 2:Getting started with serial chunking 2
Question meaning: Given a sequence of length $n(1 \le n\le 50000)$, as well as $n$ operations. The operation involves interval addition and asks for the number of elements less than a certain value $x$ in the interval.
Analysis: Ask about the number of less than $x$ in the range. If there is no modification, it can be solved by using the chairman tree. After bringing the modification, it will be difficult to maintain the chairman tree. Consider using chunking.
After chunking, you can sort the elements in the block (not destroying the original sequence, use auxiliary arrays or vectors). When asking, you can quickly solve the problem by looking up binary within the entire block, and the beginning and end parts are simple queried, so the complexity of a single query is $O(L+t*\log{L})$ .
Interval modification, for the whole block, directly modify the $lazy$ tag, naively modify the beginning and end parts, and then reconstruct the auxiliary array.
Reference code:Click
Example 3:P4168 Dandelion
Question meaning: Given a sequence of length $n$, $m$ asks the interval mode. $(1 \leq n \leq 40000,1 \leq m \leq 50000,1S,512M)$
This question is classicOnlinebegInterval modeQuestion (not modify, only ask, online). The interval mode does not have "Interval additive", it is difficult to maintain with tree-like arrays and line segment trees. It can be solved by using the idea of chunking and counting bucket arrays.
Define the number of times $s[i][j]$ before $i$ block $j$ appears, $f[i][j]$ mode from i-th block to j-th block, and calculate these two preprocessing in advance Array, time complexity $O(\sqrt{N}|a_i|+\sqrt{N}\times \sqrt{N} \times \sqrt{N})$,$|a_i|$ represents the value of $a_i$ Domain, after discrete, it is $N$
A temporary count array $t[j]$ is required to record the number of times $j$ occurs. In order to clear the zero, do not use the memset every time. After using it, modify the entire team and clear the zero.
Ask for the $[l,r]$ interval mode, if $p=l/len,q=r/len$( $p$,$q$ represents the block number in which it is located), $p+1$ to $ The q-1$ block is contained in the entire segment, and the mode is $f[i][j]$, local $[l, ed[p])$ and $[st[q],r]$ to scan each number. , calculate the number of occurrences, the number with the most occurrences is the answer, the query time complexity is $O(m \times ( \sqrt{N}+ \sqrt{N}))$
Reference code:Click
Other examples:
P3372 【Template】Segment Tree 1
//Realize interval modification and interval query in blocks
//Segment Tree Template-1
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int T=1000;
int n,m,a[N], belong[N];
int t,len; //t block =ceil(sqrt(t))
long long sum[T],add[T],st[T],ed[T];
//belong[i] means that a[i] is in which block
//st[t], ed[t] represents the t-th fastest left endpoint and right endpoint corresponding to the original array subscript
void init()
{
len=sqrt(n);
t=len;
for(int i=1;i<=t;i++)
{
st[i]=(i-1)*len+1;
ed[i]=i*len;
}
if(ed[t]<n)
{
t++;
st[t]=ed[t-1]+1;
ed[t]=n;
}
for(int i=1;i<=t;i++)
for(int j=st[i];j<=ed[i];j++)
{
belong[j]=i;
sum[i]+=a[j];
}
}
void modify(int l,int r,int d)
{
int p=belong[l],q=belong[r];
if(p==q)
{
for(int i=l;i<=r;i++)a[i]+=d;
sum[p]+=(r-l+1)*d;
}
else
{
for(int i=p+1;i<=q-1;i++)add[i]+=d;
for(int i=l;i<=ed[p];i++)a[i]+=d;
sum[p]+=(ed[p]-l+1)*d;
for(int i=st[q];i<=r;i++)a[i]+=d;
sum[q]+=(r-st[q]+1)*d;
}
}
long long query(int l,int r)
{
int p=belong[l],q=belong[r];
long long ret=0;
if(p==q)
{
for(int i=l;i<=r;i++)ret+=a[i];
ret+=(r-l+1)*add[p];
}
else
{
for(int i=p+1;i<=q-1;i++)ret+=sum[i]+add[i]*(ed[i]-st[i]+1);
for(int i=l;i<=ed[p];i++)ret+=a[i];
ret+=add[p]*(ed[p]-l+1);
for(int i=st[q];i<=r;i++)ret+=a[i];
ret+=add[q]*(r-st[q]+1);
}
return return return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
init();
While(m--)
{
int op,x,y,k;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&x,&y,&k);
modify(x,y,k);
}
else
{
scanf("%d%d",&x,&y);
printf("%lld\n",query(x,y));
}
}
return 0;
}P2801 The Magic of the Leader
Question: Two operations:
1. Add a number $c$ to the interval $[l,r]$;
2. Query the number of intervals $[l,r]$ greater than or equal to $c$
Analysis: You can use chunks, sort in each block, and the block is ordered. You can use binary search to find the number of more than or equal to $c$, but you cannot sort it on the original sequence, otherwise you will modify it to the block. Inside, there is no way to modify it. You can add an auxiliary array, with the length equal to the original array, and sort it in the auxiliary array.
If divided into $num$ blocks, the block length is $n/num$, and the block is modified and queryed directly within the block. The block is modified as a whole. You only need to modify it on the "incremental array". When querying, it is ordered. Search on the array in binary. q modification and query, the time complexity is: $O(q\sqrt{n} \log_{}{n})$
Reference code:Click
The essence is the big problem of the interval $k$. For the static interval $k$, it is more efficient to use a persistent segment tree. For details, you can refer to segment tree 2.
P4135 Poetry
Question meaning: Given a sequence of integers of length $n$, the number of positive even numbers appears in the interval $[l,r]$ in $m$. ($1 \leq n,m \leq 10^5,512M$)
Preprocessed: $s[i][j]$ is the number of times $j$ appears in the previous $i$ block, and $f[i][j]$ is the $i$th block to the $j$ block The number of even numbers.
P5048 Ynoi2019 Simulation Yuno loves sqrt technology III
Question meaning: Give you a sequence of $a$ with a length of $n$, $m$ to query, each time you query the number of occurrences of a mode of an interval, force online. ($1 \leq n,m \leq 10^5,2S,62M$)
This question can be solved with the same idea as dandelion.
Other block exercises:
1.P5046 [Ynoi2019 Simulation Competition] Yuno loves sqrt technology I
Question meaning: Give you an arrangement of $n$, $m$ inquiry, each time query the inverse logarithm of an interval, force online.
2.P5047 [Ynoi2019 Simulation] Yuno loves sqrt technology II
Question meaning: Give you a sequence of $a$ with length $n$, $m$ inquiry, querying the inverse logarithm of an interval each time.
P6774 [NOI2020] Tears of the Times
Enhanced version of the interval positive order, block + constrained
[P1494 National Training Team] Xiao Z's Socks](/problem/P1494)
Question meaning: Given a sequence of length $N$, ask $[l,r]$ for any probability of drawing two identical numbers.
Analysis: If you use the block directly, you will get T-dropped, and you can use Team Mo.
A single point movement needs to be calculated, and the total number of methods for the interval $[l,r]$ is $C_{r-l+1}^2$.
The number of the same method in the draw is $sum$, and $col[x]$ represents the number of $x$.
When $x$ is added, the same number of methods are drawn $sum+=col[x]$, and then $col[x]++$.
When deleting $x$, first $col[x]++$, the same number of methods $sum-=col[x]$.
Reference code:Click