[算法学习笔记02]分块应用

# [算法学习笔记02]分块应用
### 每日蒟蒻小故事（1/1）
蒟蒻考完 CSP 回到 S1 ，开始（和 S2 一起）新一轮的S组学习。

第一周， 学校学习的内容是分块应用。

蒟蒻尝试听懂，并听懂了 $\huge\frac{1}{3}$ 的内容。

被五年级小朋友吊打的蒟蒻想学懂分块应用。

“所以……什么是分块应用呢？”
### 什么是分块应用？

蒟蒻上了 OI Wiki 查找相关内容。

> 其实，分块是一种思想，而不是一种数据结构。

> 从 NOIP 到 NOI 到 IOI，各种难度的分块思想都有出现。

>分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

>分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。

>分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。

>当然，分块的缺点是渐进意义的复杂度，相较于线段树和树状数组不够好。

>不过在大多数问题上，分块仍然是解决这些问题的一个不错选择。

蒟蒻大概理解了分块应用的基本内容。

“来一道题让我深入理解一下！”
### A.数列分块2
>给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的元素个数。