题目内容

小美是一个热爱收藏的年轻人，他喜欢收集各种有趣的物品，例如邮票、硬币、瓶盖等等。他的收藏品越来越多，于是他决定为自己在收藏架上建了一排 $n$ 个收藏夹，分别编号为 $1,2,3…n$。这样，他就可以更好地组织和展示自己的收藏品了。

小美有些时候会突发奇想改变某一个收藏美里的内容，例如从中拿入、拿出一些藏品，这些的操作会改变小美对这个收藏夹的欣赏程度，我们记编号为 $i$ 的收藏夹，小美对其的欣赏程度为 $a_i$ 。小美在休息时间经常会欣赏连续编号的收藏夹，例如编号为 $L,L+1,L+2,...,R-1,R$ 的这些收藏夹，他能从中获得的满足感为这些收藏失的欣赏程度之和，即 $\sum ^R _{i=L} a_i$ 。

小美想在欣赏之前提前估算自己能得到的满足感，想知道如果他选择编号区间为 $[L,R]$ 的收藏夹，能给他带来的满足感是多少。但是小美不想自己计算，所以他想你帮他计算一下，然后告诉他。

题目思路

思路:树状数组模板题

转化题意之后，问题变为:给定一个序列，需要维护两类操作:单点修改值 + 区间查询和 . 这是经典的树状数组(BIT)的应用,简称裸题/模板题。我们可以做到$O(log\ n)$ 的修改和查询。

没有接触过的同学，塔子哥在此推荐以下几个学习网站:

1.B站视频-完全理解并深入应用树状数组