分块和树状数组的巧妙结合

# 背景 某天，$xk$ 正在学习树状数组。此时，老师正在讲分块，用以过渡到树状数组。 放上$ppt$:  然后，老师就开始讲树状数组了...... # 故事 某天 $xk$ 正在睡觉， $Ta$ 正在思考区间查询和修改的最优复杂度。$Ta$ 想到了常用的三种数据结构：分块、树状数组和线段树。$Ta$ 回想起学树状数组时，~~是多么的美好~~老师分块的方法。这样的方法中对于每个块都是有前缀和在维护的，而暴力修改也是针对前缀和进行暴力，那为什么不把这个前缀和替换为树状数组呢？ > $\tiny\texttt{注：这里暂时特指单点修改和区间查询。}$ 这样~~淦（可恶的输入法）~~ 干，就可以将块内的暴力时间缩减为 $O(log{\sqrt{n}})$ ，也许你会问那对于询问外面的块的时候还不是需要 $O(\sqrt{n})$ 的复杂度？ 顺着刚刚的思路，每个块累加的暴力，不也正可以用树状数组来优化吗？这样下来，每个块的暴力，就也变成了$O(log{\sqrt{n}})$的复杂度。 总结一下， $xk$ 这天晚上想到的就是$\color{red}\huge\texttt{分块套树状数组}$。 至此，故事讲完了~~请勿吐槽啥情节都没有~~。 # 思考 既然可以做到 $O(log{\sqrt{n}})$ 的单点修改和区间查询，那么该如何支持区间修改和区间查询呢？ ### $way$ $1$ 仍然利用刚刚的 $\color{red}\small\texttt{分块套树状数组}$ 可不可以呢？答案是肯定的。利用容斥原理和两个这样的数据结构就可以做到。具体做法可以类比树状数组，这里不再赘述，如果不清楚的还可以看看这张$ppt$（这是树状数组的）:  ### $way$ $2$ 既然树状数组可以套，那线段树嘞？当然也是可以的啦。但是需要注意的一点是，$\texttt{分块的常数*线段树的常数=巨大的常数}$，~~然后就没有然后了~~。 # $\small\texttt{但是请注意}$ 你以为你学到了一个非常高深而高效的东西？ 对不起： $$O(log{\sqrt{n}})=O(log{n^{\frac{1}{2}}})=O(\frac{log{n}}{2})\approx O(log{n})$$ 具体一点，用人话来讲就是$\tiny\texttt{这篇文章啥用没有。}$ ~~请不要打我~~。 ~~请留下一个赞再走吧/xyx~~。