【数据结构】树状数组拓展应用

【引子】A Tiny Problem with Integers
这里是树状数组的区间修改和单点查询
给定长度为$N(N \leq 10^{5})$的数列$A$,然后输出$Q(Q \leq 10^{5})$行操作指令;
第一类指令形如”$C\ l\ r\ d$”,表示把序列第$l~r$的数加$d$。
第二类指令形如”$Q\ x$”,表示询问序列中第$x$个数的值。

我们可以通过增强版的树状数组来求解这个问题。

新建一个数组$b$,初始为全0,对于每条指令”$C\ l\ r\ d$”,转化成以下两条指令:
①把$b[l]$加上$d$;
②把$b[r + 1]$减去$d$。
执行完后就可以考虑$d$的前缀和的情况:
①对于$1 \leq x < l$,前缀和不变;
②对于$l \leq x \leq r$,前缀和增加了$d$;
③对于$r < x \leq N$,前缀和不变($l$处加$d$,$r + 1$处减$d$,抵消了)。
可以看出$d$的前缀和就反应了指令①,所以可以用一个树状数组来维护$d$的前缀和(对$d$只有单点增加操作)。因为各次操作具有区间可加性,所以在树状数组上查询前缀和,再加上$a[x]$的初始值,就得到了$Q\ x$的值。

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注