维护区间信息（在线）

暴力做法，\(O(n)\)修改，\(O(n)\)查询。

但我们会发现多次询问会重复查询一些点，所以我们可以记录下一些区间的信息，

查询时就可以节约时间。

但我们记录的区间必须满足一些优秀性质：

灵活性：记录下的区间组合灵活性高，即查询区间可以尽可能被记录下来的区间记录下来。

高效性：记录下的区间需要能够在合理的时间复杂度类维护，且数量少。

线段树

利用平衡满二叉树。

优点：

灵活性极高，因为任意一个区间都分割为log个线段树中的节点对应的区间。

高效性，可以\(O(logn)\)的时间查询区间。

缺点：

但维护这些区间需要合并更小的区间，但区间的合并有时会很困难。

且区间修改的维护需用lazy标记，lazy标记的叠加有时会很困难。

分块

优点：

灵活性一般，因为任意一个区间都分割为\(\le\sqrt n\)个记录区间和\(\le \sqrt n\)个散点。

维护区间较为容易，因为大部分时候维护区间和散点较为暴力。

缺点：

高效性差，需要\(O(\sqrt n)\)的时间查询区间，这使得分块的题有时需要各种卡常。