简介

树状数组是一种支持单点修改和区间查询的数据结构。

实现方法

首先，定义 lowbit(x) 为 x & -x。
则树状数组第 $i$ 位管辖原数组区间右端点为 $i$，长度为 $lowbit(i)$。

单点修改

若要在第 $x$ 位增加 $k$，如下:

// c为树状数组, n为长度
for(int i = x; i <= n; i += lowbit(i)) 
  c[i] += k;

区间查询

若要查询 $[1, x]$ 的总和，如下:

// c为树状数组, res为结果
for(int i = x; i >= 1; i -= lowbit(i)) 
  res += c[i];

这样就可以用类似前缀和的查询方法实现区间查询了。

区间修改和单点查询

只要把树状数组作为原数组的差分数组即可。