返回目录

---

树状数组，其实是一个数组！！

这，是一个普通数组

a[11]={0,1,2,3,4,5,6,7,8,9,10};

如果想要求区间和，那么他的代码是这样的

for(int i=s;i<=e;i++){
    sum+=a[i];
}

每次的时间复杂度最糟糕为 $O(n)$

如果你要找 $m$ 次，时间复杂度可能达到$O(nm)$

都二元二次了，这无疑是费时的！

那么这时候，就得请出我们的前缀和数组了！

for(int i=1;i<=n;i++){
    f[i]=f[i-1]+a[i];
}

他的原理就是每一个数都是原数组前面的数的总和

演示如下

每次要算区间和，只需这样

sum=f[i];

哇撒，时间复杂度竟然只有区区 $O(1)$

就算再来 $m$ 次，时间复杂度也只会变成 $O(m)$

那么他有什么缺陷吗？

当然有!!! 毕竟哪有出题人这么善良

来看这题

【模板】树状数组 1

在这题中，原数组的值会不断地变化！

那么如果更改的是第一个数据，那么前缀和数组将从第一个开始慢慢的更改

a[1]=999;
for(int i=1;i<=n;i++){
    f[i]=f[i-1]+a[i];
}

天呀，时间复杂度竟然达到了恐怖的 $O(n)$

那么运行个 $m$ 次，时间复杂度将来到 $O(nm)$

也没比原来快多少了

所以这时候该请出谁来了呢

当然是树状数组啦! 题目都说是树状数组模板题了

我们把上面的原数组列出来

在把他们两个两个分成一个个组

把每组的和算出来，并让他成为这个组的跟，并把跟再分组，在算出他们的跟，你就得到了一个树

这个数有什么用呢?

前两个数的总和我们能看出来吧，为3

前四个数的总和为10，前6个数的总和为11+10，前8个数的总和为36

发现没有，树中的数在求和时有一些是完全不需要的，可以舍弃的，因为他们的数可以直接看他们的跟就能看出，不需要通过他们来计算(例如第一行的第二个数，他的根已经算出前两个数之和，就不需要他了)

把他们剔除，我们就得到了这棵树的简洁版

看见没，他们正好可以表示为一个一维数组

如图

你发现没，这个数组比原来的少了两个元素，其实是因为把他们加上太麻烦了，我给删了，这样正好可以组成一个二叉树

每次要获得奇数位的总和，我们只需从这个数组中拆出一部分来

例如我要前7个数的总和，可以直接算出，为7+11+10=28

时间复杂度仍然为 $O(1)$

但是修改数据的时候不同，每次修改一个数据，只需要在树中把他的祖先给改了就行，时间复杂度大大缩减，就算是最糟糕的时候，他的时间复杂度为 $O(n log n)$。

那么怎么确定他的祖先呢？

来看这个函数

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

如果你将树状数组的每个数据的下标代入后，你就会惊奇的发现！

算出来的值正好代表了他们所包含的数据的数量

例如，第8个数据代表了前8个数的总和，这个函数代入8的值即为8；第6个数据代表了前2个数的总和，这个函数代入6的值即为2。

为什么呢，在上面被删掉的数据中，都是在每一行的偶数位上(因为每一行偶数位上的数都在那一组的末尾，可以直接用他的根，不需要他)

留下的第四位数的下标为 $4 = 2^2$ ，所以他变为2进制后最末尾的1的权值为4，而因为删除了前面代表前两个数的7，所以他正好也代表了前面四个数之和。

所以每个下标变为2进制后最末尾的1的权值正好为他所代表的和的数据数量(这和他是二叉树有直接原因，但是太长了不写)

那么这个函数为什么可以求出每个下标变为2进制后最末尾的1的权值呢？

看这道题的题解你就明白了

lowbit()函数

然后告诉你求根的方法结束此篇吧

c[i+lowbit(i)]

对，就是这么简单