树状数组（Binery Index Tree）

# 树

## 树状数组（Binery Index Tree）

### 简介
其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题，现多用于高效计算数列的前缀和， 区间和。  
它可以以 {\displaystyle O(\log n)} O(\log n)的时间得到任意前缀和 {\displaystyle \sum _{i=1}^{j}a[i],1<=j<=N} {\displaystyle \sum _{i=1}^{j}a[i],1<=j<=N}，并同时支持在 {\displaystyle O(\log n)} O(\log n)时间内支持动态单点值的修改。空间复杂度 {\displaystyle O(n)} O(n)。

### 基本操作

#### 预备函数（O(1)）
```c++
int lowbit(int x)
{
    return x&(-x);
}
```

#### 新建数组（O(lgn)）
```c++
void build()
{ 
    for (int i=1;i<=MAX_N;i++)
    {
        BIT[i]=A[i];
        for (int j=i-1; j>i-lowbit(i); j--)
            BIT[i]+=A[j];
    }
}
```