块状数组

介绍

定义

将长度为 $n$ 的数组分成大小为 $k$ 的块，共有 $m=\lceil \frac{n}{k} \rceil$ 个块

最后一个块可能不完整。

核心思想

• 大段维护：维护整块信息或懒标记，复杂度 $O(m)$
• 局部朴素：块内信息暴力处理，复杂度 $O(k)$

复杂度分析

• 整体复杂度 $O(m + k)$
• $k=m=\sqrt{n}$ 时复杂度最低，即 $O(\sqrt{n})$

根据均值不等式: $k + m \geq 2\sqrt{km}$

应用

几乎所有区间查询问题，甚至线段树不能处理的问题

• 区间和
• 区间最大值
• 区间第k小
• …

图示

存储

• 全局信息
  • 元素原始信息
  • 元素所属块
  • 块数与块长
• 块内信息
  • 整块信息
  • 左右边界
  • 懒标记

以区间和为例

struct Block{
    int sum = 0; // 块内和
    int l = 0, r = 0; // 块边界
    int add = 0; // 区间加懒标记
};
// 原始数组 和 元素所属块
vector<int> arr, belong;
// 块数组
vector<Block> block;
// 块数与块长
int num = 0, len = 0;

操作

预处理

• 计算块长与块数 （全局级）
• 标记块的边界 （块级）
• 标记元素所属块并计算块内和 （元素级）

// 1-based 数组 a
void init(vector<int> &a){
    int n = a.size();
    arr = a;
    // 块长
    len = sqrt(n * 1.0);
    // 块数（有余数时多加一个不完整块）
    num = n / len + (n % len != 0);
    // 块数组（1-based）
    block.resize(num + 1);
    for(int i = 1;i <= num;i++)
        block[i].l = (i - 1) * len + 1,
        block[i].r = i * len;
    // 单独处理最后一个块
    block[num].r = n;
    // 块内和与归属标记
    for(int i = 1;i <= num;i++)
        for(int j = block[i].l;j <= block[i].r;j++)
            block[i].sum += arr[j], 
            belong[j] = i;
}

单点更新

直接更新该元素和所属块信息

void add(int pos, int val){
    arr[pos] += val;
    block[belong[pos]].sum += val;
}

单点查询

直接查询该元素信息，并叠加所属块懒标记

int query(int pos){
    return arr[pos] + block[belong[pos]].add;
}

区间更新

• 完全覆盖块：打懒标记
• 部分覆盖块
  • 逐项更新元素
  • 更新整块信息

void add(int l, int r, int val){
    // 找到区间最左块和最右块
    int p = belong[l], q = belong[r];
    // 在一个块内，暴力更新
    if(p == q){
        for(int i = l;i <= r;i++) 
            arr[i] += val, block[p].sum += val;
        return;
    }
    // 处理完全覆盖块，打懒标记
    for(int i = p + 1;i <= q - 1;i++) 
        block[i].add += val;
    // 处理左右块，暴力更新
    for(int i = l;i <= block[p].r;i++)
       arr[i] += val, block[p].sum += val;
    for(int i = block[q].l;i <= r;i++)
      arr[i] += val, block[q].sum += val;
}

区间查询

• 完全覆盖块
  • 逐块累加块内信息
  • 累加懒标记
• 部分覆盖块
  • 逐项累加元素
  • 累加懒标记

int query(int l, int r){
    int p = belong[l], q = belong[r], res = 0;
    // 在一个块内，暴力查询
    if(p == q){
        for(int i = l;i <= r;i++) res += arr[i];
        return res;
    }
    // 处理完全覆盖块，累加块内信息和懒标记
    for(int i = p + 1;i <= q - 1;i++) 
        res += block[i].sum,
        res += block[i].add * len;
    // 处理左右块，暴力查询
    for(int i = l;i <= block[p].r;i++) 
        res += arr[i] + block[p].add;
    for(int i = block[q].l;i <= r;i++) 
        res += arr[i] + block[q].add;
}

复杂度

• 单点更新：$O(1)$
• 单点查询：$O(1)$
• 区间更新：$O(\sqrt n)$
• 区间查询：$O(\sqrt n)$