块状数组的基本用法：把数组变成灵活的积木

生活中处处可见分块思想的影子。走进图书馆，书籍按照学科分类，读者只需先定位大类别，再在小范围内查找，就能快速找到目标书籍；小区的快递柜更是将大量包裹按照格口大小和编号分块存放，快递员按区域投放，收件人按编号取件，极大提升了物流效率。这种 “先整体划分，再局部处理” 的思路，在算法世界中演变成了一种高效的数据结构 —— 块状数组。
在处理数组问题时，我们也可以使用分块思想构建块状数组。
将一个长度为 \(n\) 的线性数组，按照一定规则分割成若干个连续的子数组（我们称之为 “块”）。每个块的大小通常设定在  \(\sqrt n\) 左右（取得块大小和块数量的平衡）。例如，对于长度为 100 的数组，我们可以将其划分为 10 个块，每个块包含 10 个元素；若数组长度为 1000，则可分成 32 个块（因为 √1000≈31.62），前 31 个块各含 32 个元素，最后一个不完整块包含剩余的 28 个元素。

1. vector<vector<int>> init_block_array(const vector<int>& arr) {
2.     int n = arr.size();
3.     if (n == 0) return {};
4.     int block_size = ceil(sqrt(n)); // 向上取尽可能避免最后的大小极小的块
5.     int block_num = (n + block_size - 1) / block_size; // 计算总块数
6.     vector<vector<int>> blocks(block_num);
8.     for (int i = 0; i < n; ++i) {
9.         int block_idx = i / block_size; // 计算元素所属块编号
10.         blocks[block_idx].push_back(arr[i]);
11.     }
12.     return blocks;
13. }

复制代码

这样一来，原本线性排列的数组就被 “拆解” 成了若干个可独立操作的 “积木块”，为后续的区间操作奠定了基础。
从内存结构上看，块状数组相当于在原数组的基础上增加了一层 “块级索引”，这层索引就像图书馆的区域导视图，让我们能批量快速的编辑这些 “区域”。
块状数组的基本用法

块状数组的真正价值，在于它能像搭积木一样灵活处理数组的区间操作。当我们需要对一个连续区间进行更新或查询时，不必逐个遍历元素，而是可以利用 “块” 的特性批量处理，大幅提升效率。仅仅在区间边界处理单个数。
区间加 - 区间和问题

这个经典问题可以用各种数据结构话花式解决，分块也可以。核心是为每个块维护两个关键信息：加法标记和块内元素和。加法标记记录了需要对整个块执行的累加操作，类似于给一整箱积木贴上 “每个积木加 3” 的标签；块内元素和则预先存储了当前块所有元素的总和，避免每次查询时重新计算。
以区间加操作为例子，我们将目标区间分为三部分处理：

• 左侧边缘块：区间起始位置所在的不完整块，需要逐个遍历元素执行加法操作，并同步更新块内元素和。
  
• 中间完整块：完全包含在目标区间内的块，直接更新其加法标记（如将标记值 + 5），同时通过 “块大小 × 增量” 快速更新块内元素和，而不处理中间块之中的元素。
  
• 右侧边缘块：区间结束位置所在的不完整块，处理方式同左侧边缘块。
  

最佳块大小的数学证明

这种处理方式的巧妙之处在于，完整块的操作只需 \(O (1)\) 时间，而边缘块最多涉及两个块。
为什么块大小选择 \(\sqrt n\) 能达到最优效率？假设块大小为 \(s\)，总块数则为 \(n/s\)。对于任意区间操作，最多需要处理 2 个边缘块（共 \(O (s)\) 时间）和 \(O (n/s)\) 个完整块（共 \(O (n/s)\) 时间）。总时间复杂度为 \(O (s + n/s)\)，根据均值不等式， \(s = \sqrt n\) 时，复杂度达到最优的 \(O (\sqrt n)\)。
一般来讲，取根号都是最优的，达到了块大小和块数量的平衡。某些特定情况可能需要取其他的块大小。
[code]struct BlockArray {    vector arr;         // 原始数组    vector sum;   // 每个块的元素和    vector add;         // 每个块的加法标记    int block_size;          // 块大小    int block_num;           // 块数量    BlockArray(const vector& data) {        // ...        // 初始化块内和        for (int i = 0; i < n; ++i) {            int bid = i / block_size;            sum[bid] += arr;        }    }    // 区间[l, r]加val    void range_add(int l, int r, int val) {        int left_bid = l / block_size;        int right_bid = r / block_size;        // 只有一块        if (left_bid == right_bid) {            for (int i = l; i