树状数组

树状数组的结构

a[x]表示原数组，c[x]表示前缀和数组

c[x]=(x-lowbit(x)]

lowbit(x)=2^k 表示求出x的二进制最后有k个0

我的一些理解 c[x]为到大于等于x层级之前的x'之间的a[x]之和，用公式表示就是上面的公式，二进制的原理。

##树状数组的功能 1.单点修改：在某个位置上加上一个数 O(log n)
2.区间查询：求一个前缀和 O(log n)

树状数组是一种在线的算法，可以在修改某个点的值之后继续求前缀和吗，也是和前缀和算法的去区别。

树状数组的操作代码

树状数组的的下标从1开始

int lowbit (x)
{
<!-- keywords:key1;key2; -->
<!-- description:this is a description -->
<!-- coverimage:![cover](cover.jpg) -->


    return x&-x;
}

int main () 
{
   for (int i=1;i<=n;i++)    初始化
    add(i,a[i]);
}

void add (int x, int v) 单点修改
{
    for (int i=x;i<=n;i+=lowbit(i))
        tr[i]+=v;
}

int query (int x) 区间查询
{
    int res=0;
    for (int i=x;i;i-=lowbit(i))
    res+=tr[i];
}

---

本文章使用limfx的vscode插件快速发布