块状数组（分块）

What · 是什么

块状数组（分块，sqrt decomposition）把长度为 n 的序列切成约 O(√n) 个块，每块长度约 O(√n)。块内元素整体维护聚合信息（如 lazy 加法标记、块内排序数组），跨块的区间操作只需对整块 O(√n) 个块做整体处理，而两端的散块（部分被覆盖的块）直接暴力修改后重构。它把「区间修改/区间查询」这类线段树能处理的问题推广到需要「块内排序二分」等不可线段树维护的操作上（如查询区间内 ≥z 的数的个数），代价是单次操作 O(√n log n)。

Why · 为什么

How · 实现

伪代码

# 区间加 + 查询区间内 >= z 的个数
def Range_Add(l, r, c):
  bl, br = belong[l], belong[r]
  if bl == br:
    for i in l..r: a[i] += c
    Sort(bl); return
  for i in l..块尾: a[i] += c      # 散块
  for i in 块头..r: a[i] += c
  Sort(bl); Sort(br)
  for b in bl+1..br-1: lazy[b] += c  # 整块打标记

def Count_GE(l, r, z):
  bl, br = belong[l], belong[r]
  ans = 0
  if bl == br: return 散块逐个判断 a[i]+lazy[bl] >= z
  for i in l..块尾: if a[i]+lazy[bl] >= z: ans += 1
  for i in 块头..r: if a[i]+lazy[br] >= z: ans += 1
  for b in bl+1..br-1:
    ans += 块长 - bisect_left(t[b], z - lazy[b])

Python 实现

import bisect
import math
import random


class BlockArray:
    """块状数组：区间加 + 查询区间内 >= z 的个数（洛谷 P2801 模板）。
    整块维护 lazy 标记与块内排序副本，散块暴力后重建排序。"""

    def __init__(self, arr, block_size=0):
        self.n = len(arr)
        self.a = list(arr)
        self.B = block_size or int(self.n ** 0.5) + 1
        self.nb = (self.n + self.B - 1) // self.B
        self.belong = [i // self.B for i in range(self.n)]
        self.sorted = []
        self.lazy = [0] * self.nb
        for b in range(self.nb):
            l, r = b * self.B, min((b + 1) * self.B, self.n)
            self.sorted.append(sorted(self.a[l:r]))

    def rebuild(self, b):
        l, r = b * self.B, min((b + 1) * self.B, self.n)
        self.sorted[b] = sorted(self.a[l:r])

    def range_add(self, l, r, c):
        bl, br = self.belong[l], self.belong[r]
        if bl == br:
            for i in range(l, r + 1):
                self.a[i] += c
            self.rebuild(bl)
            return
        for i in range(l, (bl + 1) * self.B):
            self.a[i] += c
        self.rebuild(bl)
        for i in range(br * self.B, r + 1):
            self.a[i] += c
        self.rebuild(br)
        for b in range(bl + 1, br):
            self.lazy[b] += c

    def count_ge(self, l, r, z):
        bl, br = self.belong[l], self.belong[r]
        ans = 0
        if bl == br:
            for i in range(l, r + 1):
                if self.a[i] + self.lazy[bl] >= z:
                    ans += 1
            return ans
        for i in range(l, (bl + 1) * self.B):
            if self.a[i] + self.lazy[bl] >= z:
                ans += 1
        for i in range(br * self.B, r + 1):
            if self.a[i] + self.lazy[br] >= z:
                ans += 1
        for b in range(bl + 1, br):
            target = z - self.lazy[b]
            ans += len(self.sorted[b]) - bisect.bisect_left(self.sorted[b], target)
        return ans


if __name__ == "__main__":
    random.seed(42)
    for n in [1, 2, 5, 17, 100, 250]:
        base = [random.randint(1, 100) for _ in range(n)]
        ba = BlockArray(base)
        brute = list(base)
        for _ in range(400):
            l = random.randrange(n)
            r = random.randrange(n)
            if l > r:
                l, r = r, l
            if random.random() < 0.6:
                c = random.randint(-20, 20)
                ba.range_add(l, r, c)
                for i in range(l, r + 1):
                    brute[i] += c
            else:
                z = random.randint(1, 200)
                expect = sum(1 for i in range(l, r + 1) if brute[i] >= z)
                got = ba.count_ge(l, r, z)
                assert got == expect, (n, l, r, z, got, expect)
    print("block-array 自测通过：随机 区间加/查询 与暴力对拍一致")

易错点

• 散块修改后必须重建排序副本，否则 count_ge 用旧排序会错
• 整块查询时要把 lazy 标记算进阈值：数 ≥ z-lazy[b] 而非 ≥ z
• l、r 同块时只做暴力并重建该块，别走到整块分支
• 块长取 √n 附近；取 1 或 n 都会退化为 O(n) 操作
• 区间加可叠加 lazy，但赋值操作（寒夜方舟类）需要 pushdown 并区分『未赋值』标记
• 归零/负数 lazy 与排序副本的交互：bisect_left 处理相等值边界要一致

例题

信源

• OI Wiki✓ https://oi-wiki.org/ds/block-array/
• CP-Algorithms✓ https://cp-algorithms.com/data_structures/sqrt_decomposition.html
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/block-array.md
• 书籍✓ CPH ch27 (p277)