树状数组和线段树的基础知识

1. 线段树能处理的问题 包含 树状数组能处理的问题
2. 而树状数组相对于线段树的优点：代码短；运行效率高

树状数组

1. 能解决的核心问题：动态的快速求前缀和
2. 可以在 $O(logn)$ 的时间内，① 给某个位置上的数加上一个数（单点修改）；② 求某一个前缀和（区间查询）
3. 对比一下前缀和，单点修改是 $O(n)$ （若修改某一个数，前缀和数组从这个数开始都会改变），区间查询是 $O(1)$
4. 如果只有区间查询，前缀和更好（$O(1)$ 优于 $O(logn)$）；如果两个操作都要有，树状数组更好（$O(logn)$ 优于 $O(n)$）

1. 如何实现？ （树状数组C是一维数组）
   $$\begin{align} &C\left[ 1 \right] =A\left[ 1 \right] \\ &C\left[ 2 \right] =A\left[ 2 \right] +C\left[ 1 \right] =A\left[ 2 \right] +A\left[ 1 \right] \\ &C\left[ 3 \right] =A\left[ 3 \right] \\ &C\left[ 4 \right] =A\left[ 4 \right] +C\left[ 3 \right] +C\left[ 2 \right] =A\left[ 4 \right] +\ldots +A\left[ 1 \right] \\ &C\left[ 5 \right] =A\left[ 5 \right] \\ &C\left[ 6 \right] =A\left[ 6 \right] +C\left[ 5 \right] =A\left[ 6 \right] +A\left[ 5 \right] \\ &C\left[ 7 \right] =A\left[ 7 \right] \\ &C\left[ 8 \right] =A\left[ 8 \right] +C\left[ 7 \right] +C\left[ 6 \right] +C\left[ 4 \right] =A\left[ 8 \right] +\ldots +A\left[ 1 \right] \end{align}$$
2. 若有 $C[x]$，$x$ 的二进制表示的末尾有 $k$ 个连续 $0$，即表示它在第 $k$ 层，则 $C[x]$ 表示A数组 $(x-2^{k},\;x]$ 区间中所有数的和
3. 因为 $lowbit$ 操作： $lowbit(x) = x\;\&\;-x=2^{k}$，所以 $C[x]$ 表示A数组 $(x-lowbit(x),\;x]$ 区间中所有数的和（核心）
4. 怎么计算前缀和？（区间查询）
   
   $$S[x]=c[x]+c[x-lowbit(x)]+\dots$$
   $$for\;(int\;i\;=\;x;\;i;\;i\;-=\;lowbit(i))\;res\;+=\;C[i];$$
5. 怎么给某个位置上的数加上一个数？（单点修改）
   $要使\;A[x]+v:$ （$x$ 的父节点是 $x+lowbit(x)$）
   $$for\;(int\;i\;=\;x;\;i\;<=\;N;\;i\;+=\;lowbit(i))\;C[i]\;+=\;v;$$
   单点修改也用于树状数组 $C[x]$ 的初始化（见以下例题）
6. AcWing 1264.动态求连续区间和 和 题解
7. AcWing 1265.数星星 和 题解

线段树

1. 形式：
   
   $$区间[L,R]，分割为[L,M]和[M+1,R]，M = \left \lfloor \frac{L+R}{2} \right \rfloor$$
2. 单点修改操作：$O(logn)$
   
3. 区间查询操作：$O(logn)$
   
4. 核心函数
   ① $pushup$：用子节点信息更新当前节点信息
   ② $build$：在一段区间上初始化线段树
   ③ $modify$：单点修改
   ④ $query$：区间查询
5. 线段树的存储：（与堆的存储类似，存储到一维数组中）
   $$存储到一维数组的下标x的位置\left\{\begin{matrix} 父节点=\left \lfloor \frac{x}{2} \right \rfloor & x\gg 1\\ 左儿子=2x& x\ll 1\\ 右儿子=2x+1& x\ll 1\mid 1\end{matrix}\right.$$
6. AcWing 1264.动态求连续区间和 和 题解