树状数组学习笔记

第 $ 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\)

\(…\)