「学习笔记」树状数组
相信来到这里的 \(OIer\) 们，
都已经知道 前缀和 是什么了（不知道也不关我的事。
前缀和可以支持 \(O(n)\) 级别的预处理以及 \(O(1)\) 级别的查询区间和。
但是，
前缀和的 修改时间复杂度，却是 \(O(n)\) 级别，
这是它最大的短板。
而我们今天要介绍的 树状数组，虽然只能做到 \(O(\log n)\) 级别的查询，
但是相较前缀和，
它的 单点修改时间复杂度，能达到 优秀的 \(O(\log n)\)。
正题：
1. 核心操作
树状数组有一个 最为核心的操作：
\(lowbit\)。
顾名思义，\(lowbit\) 操作求的是十进制数 \(x_{(10)}\) 的二进制状态 \(x_{(2)}\) 的 最低位。
而这种操作非常简单,只需要一行代码：
inline int lowbit(x) {return x&-x}。
举个栗子：
\(x_{(10)}=10,x_{(2)}=1010\)，
\(-x_{(10)}=-10,-x_{(2)}=10110\)。
我们知道，负数是用 补码 存储的，所以有：
-x 与 ~x+1 相等，
于是 \(-x_{(2)}\) 与 \(x_{(2)}\) 的最低位 仍然相等。
2. 单点修改 \(\to\) 建树
接着,我们就可以开始建树。
这是一个典型的树状数组，可以发现，
图中 \(c_x\) 所管理的元素个数，正是 \(lowbit(x)\)，
因此，有以下程序：
inline int lowbit(int x)
{
return x&(-x);
}
inline void update(int x,int k) //单点修改
{
while(x<=n)
{
a[x]+=k;
x+=lowbit(x);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int x,i=1;i<=n;i++)
{
scanf("%d",&x);
update(i,x);
}
return 0;
}
说得通俗一点，
建树操作，就是对一个所有值为 \(0\) 的树状数组进行 \(N\) 次单点修改，
时间复杂度为 \(O(n\log n)\)。
3. 区间查询 \(\operatorname{and}\) 单点查询
树状数组的求和操作，
本质上是对 \(1\sim x\) 的求和操作，
其实还是前缀和的思想，
只不过，
树状数组对区间进行划分，每一段区间的和已经确定，
由此就可以做到 \(O(\log n)\) 级别查询。
inline int lowbit(int x)
{
return x&(-x);
}
inline int query(int x) //单点查询等同于长度为1的区间查询
{
int res=0;
while(x)
{
res+=a[x];
x-=lowbit(x);
}
return res;
}
/*
while(q--)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(r)-query(l-1));
}
*/
4. 区 间 修 改
终于到了最困难的操作。
若维护序列 \(a\) 的差分数组 \(b\)，此时我们对 \(a\) 的一个前缀 \(r\) 求和，即 \(\sum_{i=1}^r a_i\)，
通过 差分数组 的定义，得 \(a_i=\sum_{j=1}^i b_j\)。
进行推导：
\[\begin{aligned} &\sum_{i=1}^r a_i\\ =&\sum_{i=1}^r\sum_{j=1}^i b_j\\ =&\sum_{j=1}^i\times (r-i+1)\\ =&\sum_{j=1}^i b_j\times (r+1)-\sum_{j=1}^i b_j\times i \end{aligned} \]区间和可以用 两个前缀和相减 得到，因此只需要用 两个树状数组分别维护 \(\sum b_i\) 和 \(\sum i\times b_i\)，就能实现区间求和（剩下的结论自己感性理解。
时间复杂度：\(O(\log n)\)。
有以下程序（利用差分思想实现）：
//求和时要记得把差分转化换掉
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&in);
update(i,in-last); //差分建树
last=in;
}
for(int x,y,k;m;m--)
{
scanf("%lld%lld%lld",&x,&y,&k);
update(x,k);
update(y+1,-k);
//差分单点修改
}
总结：
树状数组相对于我们之后要学习的 线段树 相比，树状数组的代码比线段树 更短，思维 更清晰，速度也 更快，在解决一些单点修改的问题时，树状数组是 不二之选。