树状数组学习笔记

第 $ 1 $ 章：树状数组

什么是树状数组？

树状数组可以理解为一个简易的线段树。

给定 $a$ 个数，执行 $q$ 次操作：

$op=1$ 时：将 $a_x$ 改成 $y$

$op=2$ 时：询问 $a_x$ 到 $a_y$ 的和

这题显然可以用暴力做，用数组储存，操作 $1$ 复杂度是 $O(1)$ ，但操作 $2$ 的复杂度是 $O(n)$ 。绝对超时。

考虑使用树状数组。

我们定义一个数组 $b$ :

$b_1=a_1$

$b_2=a_1+a_2$

$b_3=a_3$

$b_4=a_1+a_2+a_3+a_4$

$…$