树状数组学习(一维)

** 算法描述 **

可以对给定序列进行查询和修改
查询:主要用来查询任意两位之间数据和
修改:修改单项数据值
时间复杂度: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);
    }
}