我来发个关于BIT的福利！！！！

谢谢ls提醒， 解释一下BIT是树状数组， 一种比线段树好写的数据结构，支持大部分线段树支持的操作

感谢void_rank君的搬运.. 原来我也想过搬到这边来着.
树状数组(下简作BIT)由于代码量小,常数小的缘故,一旦在适用范围内,相对于普通线段树具有一定的优势.(我不打算和zkw之类的特种线段树去拼效率和代码量...)
应当指出,BIT的一切询问的左端点都是1,但凡区间[L,R]的询问结果都要通过[1,L-1]和[1,R]这两个询问的结果来间接得到;这使得BIT的使用受到很大的限制,例如无法用RMQ(区间最值问题).但是在弄清楚这一点的基础上,可以发现,如果RMQ的询问左端点都是1,BIT仍然是可以使用的,并且在这一前提下,BIT甚至能支持单点修改的RMQ.
据此还可以弄出别的一些用法:大概大家都知道线段树套平衡树,但其实BIT套平衡树有时会是更好的选择,可以极大地减少代码量.(同样地,这只针对普通线段树)(这是void_rank在做CF某题时弄出来的玩意儿)
另外还有一点需要补充,文中关于 一维情形下的区间加减,区间求和 以及 二维情形下的矩形加减,矩形求和 的转化思想并不局限于BIT中.这里提供 bzoj 2874:训练士兵 作为一个拓展(鸣谢liouzhou_101).

三天内自顶。。

我经常用BIT套平衡树，不过二维BIT的使用远不止介绍的那么广，有时离线二维BIT可以代替树套树。