AcWing 242. 一个简单的整数问题(树状数组的区间增加与单点查询操作)

树状数组的基本用途就是维护序列的前缀和, 仅支持"单点增加"和"区间查询"操作(代码如下)
//单点增加
void add(int x, int y){
for (; x <= N; x += x & -x) c[x] += y; } //区间查询 int ask(int x){ int ans = 0; for (; x; x -= x & -x) ans += c[x]; return ans; } 我们可以构造a序列的差分来实现"区间增加". 我们新建一个b数组,起初为全0.对于指令"C l r d",我们转化成以下的操作: 1.把b[l]加上d 2.把b[r + 1]减去d 然后用树状数组来维护b序列的前缀和,可以发现b[1~x]就是对a[x]的累计增加的大小.对于"Q x"指令,我们查询b[1~x],再加上原本的a[x]即可. #include
#define int long long
using namespace s

AcWing 242. 一个简单的整数问题(树状数组的区间增加与单点查询操作)最先出现在Python成神之路。