树状数组——数组两种初始化方式+单点增加+查询前缀和+插入

对于一个正整数x可以分解成 x= 2^i1+2^i2+...2^im;

设i1>i2>i3>...>im,利用这m个数，将区间【1，x】可以分成O(logx)个小区间

 长度为2^i1的：[1,2^i1]

 长度为2^i2的：[1+2^i1,2^i1+2^i2]

长度为2^i3的：[1+2^i1+2^i2,2^i1+2^i2+2^i3]

长度为2^im的：[1+2^i1+...+2^i(m-1) , 1+2^i1+...+2^i(m-1)+2^im];

每一个区间的长度就是右边界R的二进制表示下的最小的2的次幂，记为lowbit(R)

lowbit(x)的公式为：x-(x&-x)

比如15=2^3+2^2+2^1+2^0

有四个[1,4],[5,6],[7,7][8,15]

树状数组：利用上面思想实现。

首要用途：维护序列的前缀和

对一个序列a，建立一个数组c，其中c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和。

性质：

1.每一个节点x，有c[x]保存着以x为根节点的所有叶节点的和

2.每个内部节点c[x]的子节点个数等于lowbit（x）的位数

3.除了树根以外的每个子节点的父节点都是c[x+lowbit(x)];

4.数的深度为log(N)  //N为序列a的长度

单点增加操作：

加入一个新的点的时候，和这个有关的位置只有logn个，所以时间复杂度为O(logn)

void add(int x,int y) //初始化操作，对于每个a[i]做一遍add(i,a[i]);
{
    for(;x<=N;x+=x&(-x)) c[x]+=y;
}

初始化操作：

时间复杂度O（Nlog N）利用单点增加的操作初始化：

void add(int x,int y) //初始化操作，对于每个a[i]做一遍add(i,a[i]);
{
    for(;x<=N;x+=x&(-x)) c[x]+=y;
}

时间复杂度O（N）：

加多一个前缀和数组

void init()
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1]+a[i];
        c[i]=pre[i]-pre[i-lowbit(i)];
    }
}

查询操作：

int ask(int x) //查询操作，[1,x]的前缀和
{
    int ans=0;
    for(;x;x-=x&(-x)) ans+=c[x];
    return ans;
}