树状数组学习（一维）

算法描述

可以对给定序列进行查询和修改
查询：主要用来查询任意两位之间数据和
修改：修改单项数据值
时间复杂度：log(n)

算法思想

1.数组的构建

定义 数组C A
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
…
不难看出，其实是实现了对A的数据的分别管辖，Cn的管辖数量为 将n化为二进制数后，末尾连续零的数量； 也可这样理解，n的二进制位末尾有连续的k个0 ; 则 2^k 即为Cn的管辖数量
这里介绍一种求2^k的方法，后面会用到

int lowbit(int x)
{
    return x&(-x); //运用位运算及机器补码
}

调用 lowbit(n) , 即可得出Cn的管辖数量
而Cn的管辖范围为 ： n-lowbit(n)+1 到 n

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

2.求和

令sum=0；
遍历，每次将n的二进制数最后一位1 化为 0 ，依次 sum += C[n]，n=n-lowbit(n)，直到n<=0；
sum值即为序列 1 ～ n 的总和

int make_sum(int n)
{
    int sum=0;
    while(n>0)
    {
        sum+=c[n];
        n-=lowbit(n);
    }
    return sum;
}

3.修改单项数据

对每个包含Ai 的 Cn进行修改

void modify(int n,int i,int num)
{
    while(i<=n)
    {
        c[i]+=num-a[i];
        i+=lowbit(i);
    }
}