树状数组和ST表

Binary index tree 用来解决动态前缀和问题的数据结构。

树状数组或者二叉索引树也称作Binary Indexed Tree，又叫做Fenwick树；它的查询和修改的时间复杂度都是log(n)，空间复杂度则为O(n)，这是因为树状数组通过将线性结构转化成树状结构，从而进行跳跃式扫描。通常使用在高效的计算数列的前缀和，区间和。

C1 = A1

C2 = A1 + A2

C3 = A3

C4 = A1 + A2 + A3 + A4

C5 = A5

C6 = A5 + A6

C7 = A7

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

...

C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16、

1101 = 13我们要询问13这个位置的前缀和。依次减去1即可。

1101 d[13]      有2^0=1个数

1100 d[12]       有2^2=4个数

1000 d[8]         有2^3=8个数

将上述3个加起来即可完成。

 

lowbit（）函数：

lowbit(int x)

{

   return x&(-x);

}