原理解释
树状数组是一种通过前缀和和差分的思想所进行的维护数组，从而以 \(O(\log n)\) 的时间复杂度进行修改和查询。
一共有四种修改和查询的方式，分别是：
-
单点修改 \(+\) 区间询问
-
区间修改 \(+\) 单点询问
-
单点修改 \(+\) 区间询问
-
（二维）区间修改 \(+\) 区间询问
其中利用树状数组可以高效而简洁地处理第二、三个问题，第四个问题推荐使用【模板/笔记】线段树。
查询
查询可以计算左右区间的总和，通过它们的前缀和相减求出区间和。通过上图可以发现，如果要求 \(sum_{7}\) 的值，可以发现 \(sum_{7} = tree_{7} + tree_{6} + tree_{4}\)，而 \(7,6,4\) 之间有什么关联呢？
将其转化为二进制可以看出：\(7=(111)_{2},6=(110)_{2},4=(100)_{2}\)，它们二进制中 \(1\) 的个数是不断减少的，而且减少的是最后一位，我们只需要在每一次加后将最后一位的 \(1\) 变为 $ 0 $ 即可。
维护
和查询一样，将一个数 \(tree_{i}\) 加上 \(k\)，只需要将 \(i\) 的二进制的最后的 \(1\) 加上 \(1\)，直到加的数超过了树状数组的大小。
可以定义一个函数 lowbit(x) 来求出一个二进制数的最后一位 \(1\)：
int lowbit(int x)
{
return x & -x; // 一个数的原码与上补码
}
代码实现
单点修改
void update(int x, int d) // 在第x点上加上d
{
for (int i = x; i <= n; i += lowbit(x))
tr[i] += d;
}
单点查询
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
单点修改 + 查询 主函数
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
cin >> x;
update(i, x);
}
while (m--)
{
int op;
cin >> op;
if (op == 1)
{
int x, k; cin >> x >> k;
update(x, k);
}
else
{
int x, y; cin >> x >> y;
cout << sum(y) - sum(x - 1) << '\n';
}
}
return 0;
}
区间修改 + 单点查询 主函数
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
update(i, a[i] - a[i - 1]);
}
while (m--)
{
int op;
cin >> op;
if (op == 1)
{
int x, y, k; cin >> x >> y >> k;
update(x, k);
update(y + 1, -k);
}
else
{
int x; cin >> x;
cout << sum(x) << '\n';
}
}
return 0;
}