树状数组()-其他
树状数组()
树状数组学习笔记
第 $ 1 $ 章：树状数组
什么是树状数组？
树状数组可以理解为一个简易的线段树。
列题一
给定 \(a\) 个数，执行 \(q\) 次操作：
\(op=1\) 时：将 \(a_x\) 改成 \(y\)
\(op=2\) 时：询问 \(a_x\) 到 \(a_y\) 的和
\(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\)
\(…\)
————————
树状数组学习笔记
第 $ 1 $ 章：树状数组
什么是树状数组？
树状数组可以理解为一个简易的线段树。
列题一
给定 \(a\) 个数，执行 \(q\) 次操作：
\(op=1\) 时：将 \(a_x\) 改成 \(y\)
\(op=2\) 时：询问 \(a_x\) 到 \(a_y\) 的和
\(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\)
\(…\)