跳转至

# 块状数组

## 建立块状数组

块状数组，即把一个数组分为几个块，块内信息整体保存，若查询时遇到两边不完整的块直接暴力查询．一般情况下，块的长度为 𝑂(√𝑛)O(n)．详细分析可以阅读 2017 年国家集训队论文中徐明宽的《非常规大小分块算法初探》．

下面直接给出一种建立块状数组的代码．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    num = sqrt(n);
    for (int i = 1; i <= num; i++)
      st[i] = n / num * (i - 1) + 1, ed[i] = n / num * i;
    ed[num] = n;
    for (int i = 1; i <= num; i++) {
      for (int j = st[i]; j <= ed[i]; j++) {
        belong[j] = i;
      }
      size[i] = ed[i] - st[i] + 1;
    }

其中 `st[i]` 和 `ed[i]` 为块的起点和终点，`size[i]` 为块的大小．

## 保存与修改块内信息

### 例题 1：教主的魔法

两种操作：

1. 区间 [𝑥,𝑦][x,y] 每个数都加上 𝑧 z；
2. 查询区间 [𝑥,𝑦][x,y] 内大于等于 𝑧 z 的数的个数．

我们要询问一个块内大于等于一个数的数的个数，所以需要一个 `t` 数组对块内排序，`a` 为原来的（未被排序的）数组．对于整块的修改，使用类似于标记永久化的方式，用 `delta` 数组记录现在块内整体加上的值．设 𝑞 q 为查询和修改的操作次数总和，则时间复杂度 𝑂(𝑞√𝑛 l o g⁡𝑛)O(q n log⁡n)．

用 `delta` 数组记录每个块的整体赋值情况．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    void Sort(int k) {
      for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i];
      sort(t + st[k], t + ed[k] + 1);
    }

    void Modify(int l, int r, int c) {
      int x = belong[l], y = belong[r];
      if (x == y)  // 区间在一个块内就直接修改
      {
        for (int i = l; i <= r; i++) a[i] += c;
        Sort(x);
        return;
      }
      for (int i = l; i <= ed[x]; i++) a[i] += c;     // 直接修改起始段
      for (int i = st[y]; i <= r; i++) a[i] += c;     // 直接修改结束段
      for (int i = x + 1; i < y; i++) delta[i] += c;  // 中间的块整体打上标记
      Sort(x);
      Sort(y);
    }

    int Answer(int l, int r, int c) {
      int ans = 0, x = belong[l], y = belong[r];
      if (x == y) {
        for (int i = l; i <= r; i++)
          if (a[i] + delta[x] >= c) ans++;
        return ans;
      }
      for (int i = l; i <= ed[x]; i++)
        if (a[i] + delta[x] >= c) ans++;
      for (int i = st[y]; i <= r; i++)
        if (a[i] + delta[y] >= c) ans++;
      for (int i = x + 1; i <= y - 1; i++)
        ans +=
            ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, c - delta[i]) - t) + 1;
      // 用 lower_bound 找出中间每一个整块中第一个大于等于 c 的数的位置
      return ans;
    }

### 例题 2：寒夜方舟

两种操作：

1. 区间 [𝑥,𝑦][x,y] 每个数都变成 𝑧 z；
2. 查询区间 [𝑥,𝑦][x,y] 内小于等于 𝑧 z 的数的个数．

用 `delta` 数组记录现在块内被整体赋值为何值．当该块未被整体赋值时，用一个特殊值（如 `0x3f3f3f3f3f3f3f3fll`）加以表示．对于边角块，查询前要 `pushdown`，把块内存的信息下放到每一个数上．赋值之后记得重新 `sort` 一遍．其他方面同上题．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    void Sort(int k) {
      for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i];
      sort(t + st[k], t + ed[k] + 1);
    }

    void PushDown(int x) {
      if (delta[x] != 0x3f3f3f3f3f3f3f3fll)  // 用该值标记块内没有被整体赋值
        for (int i = st[x]; i <= ed[x]; i++) a[i] = t[i] = delta[x];
      delta[x] = 0x3f3f3f3f3f3f3f3fll;
    }

    void Modify(int l, int r, int c) {
      int x = belong[l], y = belong[r];
      PushDown(x);
      if (x == y) {
        for (int i = l; i <= r; i++) a[i] = c;
        Sort(x);
        return;
      }
      PushDown(y);
      for (int i = l; i <= ed[x]; i++) a[i] = c;
      for (int i = st[y]; i <= r; i++) a[i] = c;
      Sort(x);
      Sort(y);
      for (int i = x + 1; i < y; i++) delta[i] = c;
    }

    int Binary_Search(int l, int r, int c) {
      int ans = l - 1, mid;
      while (l <= r) {
        mid = (l + r) / 2;
        if (t[mid] <= c)
          ans = mid, l = mid + 1;
        else
          r = mid - 1;
      }
      return ans;
    }

    int Answer(int l, int r, int c) {
      int ans = 0, x = belong[l], y = belong[r];
      PushDown(x);
      if (x == y) {
        for (int i = l; i <= r; i++)
          if (a[i] <= c) ans++;
        return ans;
      }
      PushDown(y);
      for (int i = l; i <= ed[x]; i++)
        if (a[i] <= c) ans++;
      for (int i = st[y]; i <= r; i++)
        if (a[i] <= c) ans++;
      for (int i = x + 1; i <= y - 1; i++) {
        if (0x3f3f3f3f3f3f3f3fll == delta[i])
          ans += Binary_Search(st[i], ed[i], c) - st[i] + 1;
        else if (delta[i] <= c)
          ans += size[i];
      }
      return ans;
    }

## 练习

1. 单点修改，区间查询
2. 区间修改，区间查询
3. 【模板】线段树 2
4. 「Ynoi2019 模拟赛」Yuno loves sqrt technology III
5. 「Violet」蒲公英
6. 作诗

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, R-G-Mocoratioen, Enter-tainer, Henry-ZHR, ksyx, ouuan, Alpacabla, chenyanlann, iamtwz, Marcythm, partychicken, StudyingFather, Tiphereth-A, zhuzeyu22
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用