树状数组

作用：

以log(n)的复杂度实现查询和修改。(类似前缀和和差分，时间复杂度更优)

理解：

1.tr[i]的意义：
( a[i-lowbit(i)] , a[i] ]
即以a[i]为右端点，长度为lowbit(i)的一段总和，lowbit(i)–即找到二进制表示的最后一个1。
2.初步理解：
任意一个数x，假设二进制表示为 …11000，我们需要求tr[x];
首先tr[x] = a数组 ( x-lowbit(x) , x ] 这一段的和，
也等于 a数组 (x-lowbit(x) , x-1 ] + a[x] ，a[x]显然已知，我们只需求前面一段。
而已知x的二进制表示为…11000 ，故x-1为 …10111。
故前面一段可改成二进制表示:
( …10000 , …10111 ]
对这一大段，显然可以分成已经求好的几段：
( …10110 , …10111 ]
( …10100 , …10110 ]
( …10000 , …10100 ]
其中每一段都已知，而且通过lowbit操作极易分段。
进而得出tr[x] 等于上述三段之和加上a[x];
上述所有操作既是对tr数组进行初始化的步骤，亦是查询操作的思想。

3.
我们最终目的是实现快速查询与修改，有前述可知，查询和初始化tr一样，都是通过不断地切分，将大段需要求的a数组之和通过多个已知小段求出(利用lowbit操作分成小段)。
而修改操作则完全相反，他是查询和初始化的逆过程。
要实现修改a[x]，难点在于不仅要修改tr[x]，还要修改其他通过a[x]/tr[x]直接或间接算出的tr[x]。
这时，我们发现修改之于另外两者是逆过程(子节点找父节点)，最关键的是逆过程是唯一的。
对于我们修改的一个x 假设为 …00110。
他的唯一父节点即为 x + lowbit(x)，即将最后一串1变为0，再进一位1，变为..01000。
这正好是..01000的分解后的一个子节点。
注意：我们一次只能找到修改x直接影响到的其父节点(x+lowbit(x))，并不能找到间接影响的父节点的父节点的…。所以我们要通过循环，直到将所有间接影响的点全部修改完为止。

结论：

建树：

//方法一(O2:n)
for (int x = 1; x <= n; x++) 
{
    tr[x] = a[x];
    for (int i = x - 1; j > x - lowbit(x); i -= lowbit(i)) 
        tr[x] += tr[i];
}
//方法二（O2:nlogn)
for (int x = 1; x <= n; x++) add(x, a[x]);

//方法三(O2:n)
{
    //计算a[N]的前缀和数组pre[N];
    tr[i]=pre[i]-pre[i-lowbit(i)];
}

修改 ：

for(int i = x; i<=n; i+=lowbit(x) ) tr[i] += c;

查询 :

(1~x) for(int i = x ; i ;i-=lowbit(x) ) ans+=tr[i];