“在批量查询终结任务中，将同一赋值轨迹产生的14条更新与8条前缀查询交给本算法，再与排序分块的在线结果核对。两边都必须按查询编号给出[4,2,5,0]，负事件是模型的一部分，不能因为“计数不应…”
形式陈述
一层块，而不是递归的树
给定长度n的数组A，选正整数块长B。非空数组取1≤B≤n；第j块为
块互不相交，按下标顺序覆盖数组。每块保存原元素和一份摘要。查询半开区间[l,r)时，将其分成左端零散项、连续完整块、右端零散项；每个位置只计一次。若两端落在同一块，就直接扫描该段，不把它误算成两个相交的边界段。
摘要决定能回答什么。例如保存每块的和，可以把完整块的和直接相加；保存每块的有序元素表，则能回答“区间中有多少个值不超过k”。本页实现后一种接口：assign(i,x) 把A[i]赋为x，count_le(l,r,k) 返回满足l≤i<r且A[i]≤k的位置数。重复值按出现位置计数。输入是整数，查询须满足0≤l≤r≤n。[1, PDF pp.4–21]
算法不要求提前知道未来查询，可以在每次赋值后立刻返回下一次查询的答案。名称中的“平方根”来自一类成本平衡，B并非必须恰等于√n。
直觉
用摘要省掉整块内部的工作
若B很小，边界扫描便宜，但一个长区间会跨越很多块；B很大，块数少，却可能要扫描很长的边界。对常数大小、常数时间可合并的摘要，一次查询成本为O(B+n/B)，B接近√n时两项平衡。
这里的“可合并”包含次序要求。字符串连接这样的非交换运算，也能按下标从左到右依次合并片段；把右边界先并入左累加器则可能改变答案。另一方面，只有两个块各自的不同值个数，不能求并块后的不同值个数，因为不知道它们出现了哪些相同的值。
排序表不改变原来的位置
每块另存一份非降排序表Sⱼ，保持“它的多重集合恰等于A在Iⱼ中的元素”。原数组仍按下标排列，所以边界部分可以逐项检查；完整块则在Sⱼ中用二分查找求第一个大于k的位置，该下标恰是≤k的元素个数。
赋值A[i]=x时，先在所属排序表中找到旧值的一次出现并删除，再插入新值的一次出现，最后改原数组。这保留全部其他位置，也保留重复元素的正确份数。删掉所有等于旧值的项，会破坏多重集合不变量。
覆盖不变量给出查询正确性
实现保存当前尚未处理的左端l和累计答案。先逐项前进到块边界；随后每次处理一个完全落在查询内的整块；余下不足B项逐项处理。每一步都恰好处理尚未计入的最左片段，因此已计入部分与余下部分不交，合起来始终等于原查询区间。
零散项直接检查定义，完整块由排序表不变量得到正确计数。循环结束时余段为空，累计值就是全部目标位置数。空区间在第一步就结束并返回零。
例子与边界
同一次查询混合两种表示
取A=[3,1,3,2,1,4,2,3]，B=3。三块原序列为[3,1,3]、[2,1,4]、[2,3]，排序表为[1,3,3]、[1,2,4]、[2,3]。求 count_le(1,7,2)：左段下标1、2只计入1；整块[3,6)贡献2；右段下标6贡献1，总数4。
执行 assign(2,1)，第一块排序表从[1,3,3]变成[1,1,3]。此后 count_le(0,4,1) 返回2。再把下标5赋成1，第二块排序表成为[1,1,2]，count_le(2,8,2) 返回5。把下标2再次赋成1，仍只删除并插回一次1，不会改变计数。
更新的快慢不能从“分块”二字推出
若摘要是和，赋值后只需将块和增加x−旧值，更新本身O(1)。若摘要是最小值，把唯一最小元素改大后，单凭旧最小值无法恢复新最小值；可以扫描整块重建，成本O(B)。排序表虽然只需O(log(B+1))次比较找到位置，但数组删除和插入要搬动最多B项，更新总成本仍是O(B)。
在[1,4,7]中删去1后，旧摘要“最小值1”无法告诉你答案是4；换成[1,5,7]，旧摘要相同，新答案却是5。这个反例说明摘要丢失的信息不能靠一条更新公式凭空恢复。
空数组没有块，只允许[0,0)查询；不能赋值某个不存在的位置。末块可以不足B项。附件把过大的B夹到max(1,n)，拒绝零、负数和非整数块长；固定长度接口不支持插入新位置。
推论与应用
分清比较成本与移动成本
对排序块实现，初始化为O(n log(B+1))，空间O(n)；一次赋值为O(B)，一次计数为
边界至多扫描2B项，每个完整块各做一次二分。B≈√n给出O(√n log(n+1))的查询上界，不能套用常数摘要版本的O(√n)。若U次更新、Q次查询已知，可用
比较候选块长，而不是无条件固定√n。这里假设下标、数值及计数装入常数个机器字，整数比较与加减为常数；大整数需要另计位成本。
在同一工作负载上选择接口
线段树用递归层次组织可合并摘要，树状数组擅长可逆的前缀聚合；排序块提供的是容易局部重建的一层结构。若请求必须立刻回答，本页实现可以直接工作。若请求全部已知且数组不变，莫队算法能重排窗口，以频次状态处理不便用小摘要合并的统计。
批量查询终结任务把上述赋值轨迹再转成CDQ三维支配事件，分别用在线排序块与离线统计核对4、2、5、0。两份答案相同，但可接收输入的时机和维护状态不同。