树状数组

树状数组用来处理前缀和问题，将前缀和按照2次幂进行划分成子段。

如果没有树状数组，我们需要合并n次才能求出前n个数的和；但是使用树状数组，我们只需要至多$\log n$次就可以计算出总和

如上图，如果要查询前七个数的和，我们只需要找到$c_7,c_6,c_4$即可。

那么如何求出$c_x$所管理的子段范围？

我们容易得知，任意$c_x$管理的长度都是2的次幂，又可知$c_x$管理的子段的右端点一定是$x$，那么根据规定, $c_x$ 管理的长度为$x$的二进制表示中最低位1和后面0组成的数

比如 $c_{10}$, $10 = [1010]_2$ ，那么管辖的长度即为[10]=2，管辖的范围为(9, 10)

那么，我们可以快速的求出$c_x$管辖的范围

int lowbit(int x) 
{
    return x & -x;
}

pair<int, int> get(int x)
{
    return {x - lowbit(x) + 1, x};
}

那么如何求出指定区间的和？

查询 [l,r] 可以先查询 [1,r] ，再查询 [1,l-1]。通过作差获得结果

根据每个管辖的范围不同，我们只需要根据管辖的长度向前跳动，就可以实现计算区间和。

int getsum(int x) 
{  
    // a[1]..a[x]的和
    int ans = 0;
    while (x > 0) 
    {
        ans = ans + c[x];
        x = x - lowbit(x);
    }
    return ans;
}

单点修改

对一个点的值进行修改，需要连带修改所有包含这个点的区间$c_x$，知道超出区间限制

void add(int x, int k) 
{
    while (x <= n) 
    {  
        // 不能越界
        c[x] = c[x] + k;
        x = x + lowbit(x);
    }
}

建树

可以视为对每一个点进行单点修改

void init() 
{
    for (int i = 1; i <= n; ++i) 
    {
        t[i] += a[i];
        int j = i + lowbit(i);
        if (j <= n) t[j] += t[i];
    }
}

或使用前缀和

// Θ(n) 建树
void init() 
{
    for (int i = 1; i <= n; ++i) 
    {
        t[i] = sum[i] - sum[i - lowbit(i)];
    }
}