分块思想：大数据处理的通用技巧

当你需要对大数据做区间操作时，线段树太复杂、树状数组功能有限——这时候"分块"就是你的万能武器。

一、什么是分块？

分块（Block Decomposition / Square Root Decomposition）：把一个大数组分成若干个小块，每个块单独维护一些信息。

核心思想：大块处理 + 小块暴力

想象一个图书馆有 10000 本书，分成 100 个书架，每个书架 100 本书：

• 你要找"第 300 到第 800 本书"
• 完整包含的书架（如第4-7书架）→ 直接查整书架的统计信息
• 边界不完整的书架（如第3书架的一部分、第8书架的一部分）→ 一本一本翻

二、具体怎么操作？

假设数组有 n 个元素，块大小 block_size = √n。

数组: [1, 3, 5, 7, 9, 2, 4, 6, 8, 10, 3, 1, 5, 7, 9, 2] 块: |--块0--| |--块1--| |--块2--| |--块3--| 1 3 5 7 9 2 4 6 8 10 3 1 5 7 9 2 sum=16 sum=21 sum=22 sum=23