树状数组

就我目前的理解来看，树状数组是进阶版的前缀和数组，在同样支持区间和查询的同时，还具备以较小的时间复杂度动态更新的能力。而在这篇笔记中，我并不想对它做具体的说明，仅记录我个人的一点感悟，原因是B站上有up主已经讲得很清晰透彻了——B站视频讲解。

感觉设计出这些数据结构的人真的很牛逼，把数组和下标之间的关系玩出花来了，实现这样一个能动态更新的“前缀和数组”，甚至也只需要一个长度为n的数组。

并且实现这样一个功能强大的树状数组，还并不需要多么复杂的代码，只需要实现三个操作即可，总共代码不会超过40行，能比较方便地在之后应用出来，这就非常爽了。

树状数组和前缀和数组的关系跟TreeSet和List之间的关系有点像，都是用稍弱一点的查询效率（O(1)到O(logn)）换更高效的更新效率，同样也为O(longn)。

学习了树状数组，也让我对前缀和数组的理解更深了，前缀和数组更适合存储的信息是不需要动态改变的信息，也就是说如果就只初始化一次，后续无需修改，那么用前缀和数组获得O(1)的查询操作是非常香的，而如果在类似于这道题E - Mod Sigma Problem中，有需要频繁更新和查询的需求，那树状数组就香多了。