树状数组、线段树

用空间换时间

差分数组 区间修改，单点查询
前缀和数组 不可修改，区间查询
树状数组 单点修改，区间查询
线段树 区间修改，区间查询

数组不变，区间查询：前缀和、树状数组、线段树；
数组单点修改，区间查询：树状数组、线段树；
数组区间修改，单点查询：差分、线段树；
数组区间修改，区间查询：线段树。

树状数组 (Binary Indexed Tree)

按二进制划分数组，记录前缀和信息

从图中我们发现，从5开始，应当被更新的位置的坐标为原坐标加上原坐标二进制表示中最后一个1所代表的数字。这一过程和上面求和的过程刚好相反。以int x = 5为例，我们可以用如下运算实现：

x = 5 = 0b00000101
-x = -5 = 0b11111011
x & (-x) = 0b00000001
x + (x & (-x)) = 0b00000110

线段树 (Segment Tree)

分治法：二分数组，记录每一段的信息