树状数组

这只是一个树状数组的笔记而已HHHH

下面开始正文

其实现在我也没太弄懂它的原理,只是...

XD

首先,我们需要把一个数转成二进制,然后找它最低位的1

怎么找呢?

我们知道,负数在计算机中的存储方式是将一个数按位取反,然后再+1

比如说:

5

可以转换为

(前面省略)0000000101

-5

则可以存储为

(前面省略)1111111010 + 1 = (前面省略)1111111011

而如果把5 & -5会怎么样呢?我们来模拟一下:

 0000000101
&1111111011
------------
 0000000001 = 1

相似地,我们可以再举几个例子:

7=0000000111;
-7=1111111000+1=1111111001

7 & -7 =

 0000000111
&1111111001
------------
 0000000001=1
12 & -12 = 
 00000001100
&11111110100
-------------
 00000000100=4

因此,我们可以发现:如果把一个数按位与上它的负数,就可以得到它最后一位1加上后面一串0的确切值啦!

注意:这样返回的并不是最后一位1的位置,而是最后一个1后面填上一串0然后转成10进制之后的值。

所以说,我们可以写出如下代码来计算某个数最后一位1再填上一串0的数

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

下面,我们还需要做的就是单点添加和区间求和问题

单点添加

void add(int pos,int num)
{
    while(pos <= n)
    {
        c[pos] += num;
        pos += lowbit(pos);
    }
}

区间求和

int sum(int q)
{
    int ans = 0;
    while(q)
    {
        ans += c[q];
        q -= lowbit(q);
    }
    return ans;
}

当然,如果我们要把某个区间全都修改成某一个值该怎么办呢?

(思考)

其实,我们可以做的是把区间开始的点加上某个值,再在区间结束的地方减去某个值就行了qwq

(这就是传说中的查分差分思想)

比如说像这样:

 scanf("%d%d%d",&o,&p,&q);//o是区间起点,p是区间终点,q是要加上的值
 add(o,q);//在o位置加上q
 add(p + 1,-q);//在p + 1位置减去q

好了,树状数组的基本操作大概就是这样。有了树状数组,你就可以更快速地进行关于普通数组的批量操作♂啦(滑稽)


发表于 2019-08-21 15:27:20 in 杂项