一些关于BIT扩展的整理

树状数组(BIT)以其代码简洁、效率高见长,但又由于它的应用弹性远不如线段树而与其在竞赛中相互制衡。 然而,对于我等手残党而言,为了尽可能避免使用线段树这种又长又难调的东西,学会增强BIT是十分必要的!

基本模型-改点球段

void update(int *d, int x, int val) {
    for (; x<=n; d[x]+=val, x+=lowbit(x));
}

int query(int *d, int x) {
    int ret = 0;
    for (; x<=n; ret+=d[x], x-=lowbit(x));
    return ret;
}

树状数组的概念啊原理啊什么的都不是本文讨论的对象,因此仅献上代码,后文的几种扩展都在此基础之上。

第一次修改-改段求点

首先分析一下BIT的作用。

不加BIT的情况下,对一个数组进行点修改的复杂度为O(1),段询问复杂度为O(n);而加入BIT之后,两个操作的复杂度都变为了O(log n)。 也就是说,他能将在O(log n)的时间内完成点修改段询问。而我们的目标是在同样的时间内完成段修改点询问

origin:  1  7  7  6  0  4  3
assist:  1  6  0 -1 -6  4 -1

设计一个新的数组assist[],使得assist[i]=origin[i]-origin[i-1]。也就是说,assist[]储存的是原数组的增量。既然如此,那么将原数组[l,r]加上val的操作便可以转化为两个对assist数组的点操作:

assist[l] += val;
assist[r+1] -= val;

因为在assist的某一位+1等于原数组中从这一位开始往后每一位都加了一。于是我们便成功的把对元数组的段修改转化为了对辅助数组的点修改。 在观察这两个数组,不难发现,sum(assist[1..i])的值即为origin[i]。因此,对原数组的点询问便可以转化为对辅助数组的段询问。

于是就明朗了。我们只需要将树状数组建立在assist数组之上即可实现该段求点。 (当初学这个的时候被误导的很深啊草)

(未完待续)