题目分析

这是一个典型的数据结构问题，要求实现一个支持区间加法和区间求和的数据结构。题目给出了 $n$ 次操作，每次操作要么是给区间 $[l, r]$ 的所有元素加上 $c$，要么是查询区间 $[l, r]$ 的和并对 $c+1$ 取模。

解题思路

方法选择：分块算法 对于这种区间操作问题，我们可以选择多种数据结构：

线段树：时间复杂度 $O(\log n)$，但代码较复杂

树状数组：只能处理部分区间操作

分块算法：时间复杂度 $O(\sqrt{n})$，实现相对简单

考虑到题目数据范围 $n \leq 50000$，分块算法的时间复杂度 $O(\sqrt{n}) \approx O(224)$ 是完全可接受的。

分块设计

将数组分成 $\sqrt{n}$ 个块

每个块的大小约为 $\sqrt{n}$

数据结构：

arr：存储原始数组

block_sum：存储每个块的和

block_add：存储每个块的加法懒标记

核心操作：

区间加法：

对于不完整块，直接暴力修改

对于完整块，更新懒标记和块的和

区间求和：

对于不完整块，暴力求和

对于完整块，直接使用块的和 算法复杂度分析 时间复杂度：

区间加法：$O(\sqrt{n})$

区间求和：$O(\sqrt{n})$

总体：$O(n\sqrt{n})$

空间复杂度：$O(n)$

关键点说明

懒标记技术：对于完整块的操作，使用懒标记避免频繁更新，提高效率

边界处理：注意处理区间两端的不完整块

索引转换：题目使用1-based索引，代码中需要转换为0-based

取模操作：只在查询时对结果取模，避免在中间计算中频繁取模

代码总结

分块算法是解决区间操作问题的有效方法，它在线段树和暴力算法之间取得了很好的平衡。虽然时间复杂度不是最优的 $O(\log n)$，但实现简单，在 $n \leq 50000$ 的数据规模下表现良好。这种方法也适用于其他区间操作问题，如区间乘法、区间最值等。