【模板】树状数组1

题目

洛谷P3374树状数组 1

题解

能够用树状数组维护的值必须满足区间加(将两个区间合并)和区间减(将一个区间拆开)(例:区间和可以加减,但区间最值只能加不能减)。树状数组的作用是动态维护区间数据和动态查询,基本用途是维护区间和(以下讲解都以区间和为例)。

lowbit运算:lowbit(n)定义为非负整数n在二进制表示下“最低位的1和其后面所有的0”构成的数值。(例子:n=10=(1010),lowbit(n)=2=(10) )

C++中,在补码表示下,~n=-1-n, lowbit(n)=n&(~n+1)=n&(-n)。

另c[x]表示序列的区间[x-lowbit(x)+1,x]中的所有数的和,于是区间[1,x]就可以分为(log x)段,相当于二进制分解的过程。(例:x=7=(111),[1,7]分成[1,4],[5,6],[7,7],区间长度分别为4,2,1)

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月26日 上午10:40

【小白解析】
本题的lowbit()操作初看非常玄乎:本质上讲,lowbit(x)是找到x的因数中,最大的2的幂,其主要目的是为1~n分段以便计算。
例:若范围为1-8,换算成二进制位0001-1000。对每一个数进行add函数中的循环,具体体现为:

1:0001(1)->0010(2)->0100(4)->1000(8)

2:0010(2)->0100(4)->1000(8)

3:0011(3)->0100(4)->1000(8)

4:0100(4)->1000(8)

5:0101(5)->0110(6)->1000(8)

6:0110(6)->1000(8)

7:0111(7)->1000(8)

8:1000(8)

可以看出,所有数字的add值都存在sum[8]中;[1,4]的add操作都存在sum[4]中;[3,4]的add操作都存在sum[4]中……
以此类推,单方向上看,1-n被分为log2(n)段;若是把个数字都看成独立的段,即可拼凑成不同长度(长度均为2的幂)的区间。
而12行的ask方法则反其道而行。
例:若需要考察[1,7]的和,则依次遍历:

0111(7):仅储存7的值

0110(6):储存[5,6]的值

0100(4):储存[1,4]的值

0000(0):循环结束;此时[1,7]的和均被遍历完毕

最后第12行中,以[1,y]之和减去[1,x-1]之和,得[x,y]之和,完毕。