0%

7.25夏令营总结

今天,我们学习了一样新的东西,那就是树状数组。何为树状数组呢?

【问题】我们定义 N 个整型变量组成的数组 v[1..N],每次操作有两种:

① 将v[idx] 增加 det

② 求 7.25夏令营总结 - 邱俊斌 - 邱俊斌

【想法】我们怎么解决好呢?

用数组直接操作,操作①O(1),操作②O(n2)。明显超时。

用线段树,代码量大,而且,容易出错。

用新学的RMQ,我们先DP求出F[i][k]表示从第i位出发的2k的和,那么求区间[1..i]的合适,就先找出k,使得1<2k≤i。得出F[1][k]后,继续求区间[2k+1,i]的和,知道2k+1=i时结束。这样,我们可以很好地求和。

但是,我们如果改变一个的值,那该怎么办呢?需要修改的地方太多了。而且,RMQ是静态的。

【引入】和RMQ的想法一样,如图,建立起F[i][k]这样一个数组,就像图中的区间一样。

他不见了。

然而,我们发现,其实,红色区域的地方,其实是没有什么用的。比如说[2]的那一块小的红色区域,可以用[1..2]的区域减去[1]区域。那么,去掉红色区域,就清晰多了。

现在,我们发现,我们可以用点i表示其中一个区间。比如说:

点1表示区间[1];

点2表示区间[1..2];

点3表示区间[3];

点4表示区间[1..4];

……

他不见了。

【低位技术lowbit】树状数组,与之息息相关的,就是低位技术。

所谓低位技术,就是取出一个二进制数,从右往左数,第一个以的位置。如[10010],那么,我们需要一种技术,取出[00010]。

① I and (I xor (I-1))。我们假设有这么一个数[10…0](代表任意数),那么减1,就变成了[…*01…1],在两者异或以下,就变成了[0…011…1],在最初的I进行与运算,则变成[0…010..0],达到了我们想要的目的。

② I and (~I+1)即I and (-I)。一个数[10…0],取反变成#…#01…1,加1得[#…#10…0],与运算得[0…010…0],同样达到了我们想要的目的。

【修改】假如,我们修改点6,那么,我们需要修改区间[5..6]和[1..8];假如我们修改点4,那么我们需要修改区间[1..4][1..8]。这其中有什么规律呢?

规律在于二进制。6的二进制是110。那么首先,我们要修改点6的值,即区间[5..6]。接着110的lowbit,就是10,110+10=1000,即8,那么,我们需要修改点8的值,即区间[1..8]。最后,1000的lowbit是1000,相加为10000,即16,超过了N,退出。

以4为例。4的二进制是100.首先要修改点[4],即区间[1..4]。然后100的lowbit为100,100+100=1000,即8,那么,我们需要修改点8的值,即区间[1..8]。最后,1000+1000=10000相加,超过了N,退出。

这样,时间复杂度是

他不见了。

【求和】同样道理,若求[1..6]的和,就是求点6和点4的和,即区间[5..6]和[1..4]的和。同样是二进制,6的二进制是110。因此,先加上点6的值。110的lowbit是10,这次是相减,110-10=100,即4,加上点4的值。100-100=0,等于0,退出。

求[1..4]也同样。4的二进制是100,因此要加上点4的值。100-100=0,等于0,退出。

这样,时间复杂度也是

他不见了。

【初始化】起初,我是不知道该如何初始化的。但是,转念一想,说是插入,不就是将第i个值增加输入的值吗?

【程序】

```c++
#include
using namespace std;

ifstream fin(“Binary_Indexed_Trees.in”);
ofstream fout(“Binary_Indexed_Trees.out”);

#define maxn 100002

int F[maxn], N, M;

int lowbit_(int x) {
return x & (-x);
}//低位技术

void add_(int idx, int x) {
for (; idx<=N; idx+=lowbit_(idx))//加上idx的低位
F[idx] += x;
}

void in_() {
fin >> N >> M;
for (int i=1; i<=N; i++) {
int a;
fin >> a;
add_(i, a);//初始化,无非就是在idx增加一个值
}
}

int sum_(int idx) {
int s=0;
for (; idx>0; idx-=lowbit_(idx)) //减去idx的低位
s += F[idx];

return s;

}

int main() {
in_();

for (int i=1; i<=M; i++) {
    char symbol;
    int pos, val;
    fin >> symbol >> pos;
    if (symbol == 'a') { //判断操作标志
        fin >> val;
        add_(pos, val);//修改
    }
    else
        fout << sum_(pos) << endl;//求和
}

return 0;

}

【感受】其实,树状数组代码短,速度快,常数小,在求和方面有着极为重要的低位,需要我们更好地去掌握。

Thank you so much.