题目分析

本题要求实现一个数据结构，支持两种操作：

区间加法：将区间 $[l, r]$ 内的所有元素加上 $c$

单点查询：查询位置 $r$ 的元素值

数据范围：$n \leq 50000$，需要高效处理操作。

解题思路

分块是一种介于朴素算法和线段树之间的算法，它将数组分成若干个块，通过对块的整体操作和块内元素的个别操作来平衡时间复杂度。

算法步骤：

分块预处理：

确定块大小 $B$（通常取 $\sqrt{n}$）

计算每个元素所属的块编号

记录每个块的左右边界

区间更新操作：

如果区间 $[l, r]$ 在同一个块内：直接遍历更新该块内的元素

如果跨越多个块：

更新左端不完整块：遍历更新

更新中间的完整块：使用懒标记记录整块要加的值

更新右端不完整块：遍历更新

单点查询操作：

返回元素原始值加上所在块的懒标记值

时间复杂度

预处理：$O(n)$

区间更新：$O(\sqrt{n})$

单点查询：$O(1)$

空间复杂度

$O(n)$

算法优势

1.简单易懂：分块思想直观，代码实现相对简单

2.效率平衡：在 $n = 50000$ 的数据规模下，$O(\sqrt{n})$ 的操作复杂度可以接受

3.通用性强：分块思想可以扩展到其他区间操作问题 代码总结 分块算法通过将数组分段处理，在保证正确性的同时提高了操作效率。对于本题的区间加法和单点查询操作，分块算法是一种简单而有效的解决方案。通过合理设置块大小，可以在时间效率和代码复杂度之间取得良好平衡。

代码总结

分块算法通过将数组分段处理，在保证正确性的同时提高了操作效率。对于本题的区间加法和单点查询操作，分块算法是一种简单而有效的解决方案。通过合理设置块大小，可以在时间效率和代码复杂度之间取得良好平衡。