树状数组学习总结

今天本初中生蒟蒻学习了一下\(\color{red}{树状数组}\)，总结一下~~~

树状数组的实现

功能简介

• 快速求前缀和（\(\color{purple}{O(log_2n)}\)）
• 修改某一个数（\(\color{green}{O(log_2n)}\)）

树状数组图示

树状数组其实就是如图所建立的~~~

下面引入一个函数——lowbit

lowbit(x)是x的二进制表达式中最低位的1所对应的值。

例如：

1. \(lowbit(6)\)
   6的二进制为\((110)_2\)，\(lowbit(6)=(10)_2=2\)
2. \(lowbit(8)\)
   8的二进制为\((1000)_2\)，\(lowbit(8)=(1000)_2=8\)

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

知道这个函数之后，我们再来看这张图~~~
对于第一行的数字，\(\color{green}{lowbit之后都等于(1)_2}\)
对于第二行的数字，\(\color{red}{lowbit之后都等于(10)_2}\)
对于第三行的数字，\(\color{purple}{lowbit之后都等于(100)_2}\)
\(\dots\)

这就是这张图的神秘之处~~~

快速求前缀和

我们再来观察这张图

如果我们想求\(C_8\)
那么\(C8=A_8+C_7+C_6+C_4\)
然后我们看一下这3个数7,6,4
\(\color{orange}{7-lowbit(7)(1)=6}\)
\(\color{pink}{6-lowbit(6)(10)=4}\)

综上所述:
\(\color{red}{C_x=C_{x-lowbit(x)} + C_{x-lowbit(x) - lowbit(x-lowbit(x))+\dots+A_x}}\)

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i]; //tr为我们的树状数组

    return res;
}

修改某一个数

还是这张图~~~

假如我们要修改的是C1，让他加上10
那么我们看一下他需要更新的点：\(C_1,C_2,C_4,C_8,C_{16}\)
再来看看他们的性质：
\(\color{orange}{1+lowbit(1)(1)=2}\)
\(\color{pink}{2+lowbit(2)(10)=4}\)
\(\color{green}{4+lowbit(4)(100)=8}\)
\(\color{blue}{8+lowbit(8)(1000)=16}\)

综上所述:\(\color{red}{对于每一个C_{x+lowbit(x)}都加上所要增加的数}，注意：x每次让其等于x+lowbit(x)\)

void add(int x, int val) //val为要加上的值
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += val; //tr是树状数组
}