【模板】树状数组2

题目

洛谷P3368树状数组2

题解

将普通树状数组操作和差分思想结合,就可以实现区间修改和单点查询。若对区间[l,r]进行修改,则在l处修改,并在r+1处反向修改。在查询时,询问x处的值,则求[1,x]的和,若x在[l,r]内,则会累加l处的修改,若x在r右侧,则r+1处的反向修改会抵消l处的修改。

代码

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

【小白解析】
此题依旧沿袭树状数组1的思想,在此基础上把区间求和转换成以单一值代表对整个区间的操作。
add(x,k)表示对于[x,n]整个区间进行加k操作。add(y+1,-k)则相应地将不包含于x,y内的区间进行减k操作。

例:若x==2,y==4,n==8,在该操作中:

以下sum[]数组成员+k:0010(2)->0100(4)->1000(8)

以下sum[]数组成员-k:0101(5)->0110(6)->1000(8)

此时仅有sum[2],sum[4]==k。

若此时考察ask(3),具体步骤为:

0011(3)->0010(2)->0000(0)

ans+=0+k,ans==k

若此时考察ask(7),具体步骤为:

0111(7)->0110(6)->0100(4)->0000(0)

ans+=0-k+k,ans==0

相似操作均可证明。
需要注意的是,sum[]数组代表操作,ans即为操作的累加,需要在最后加上原成分的值a[x]。
*突然发现这些程序内存限制上限都十分巨大……大概是我云了