[浅谈数据结构] 浅谈树状数组
1.作用树状数组是一种高效而简单的数据结构，用于*大部分区间修改和查询问题，形如\(a+a+a+a+...+a\)（其不支持的可以由线段树替代）
2.选择原因
优点：树状数组的码量明显比线段树短，时间复杂度比朴素算法与线段树更优，空间复杂度则吊打线段树
缺点：部分线段树能解决的问题树状数组解决不了
3.基本原理&实现方法
如图(from OIWiki)
在求解\(a+a+a+a+...+a\)这类问题时，根据上图这种数据结构，我们可以高效的进行查询
3.0.lowbit
3.0.1.思路
干什么的：求一个非负整数\(n\)在二进制下的最低为1的位的个数（1）及其后面的0的位数构成的数（1+后面0的个数）
怎么干:return x&(-x)
原理（不会可以跳过，但要背结论）:
我们得到lowbit的值，只需要得到最后一个1的位置，并且把除了这个位置之外的所有位置全部置成零。然后输出就可以。思路有了，如何操作？
根据计算机补码的性质，补码就是原码的反码加一
如：
\((110)_{2}\)
反码：
\((001)_{2}\)
加一：
\((010)_{2}\)
可以发现变为反码后 \(x\) 与反码数字位每一位都不同， 所以当反码加\(1\)后会逢\(1\)一直进位直到遇到\(0\)，这个\(0\)变成了\(1\)，操作停止。
进位的部分相当于再一次取反，也就还原原著。而最后变为1的部分又停在最后一个为0的位置，也就是取反前1的位置了，正好完成操作
又有人要问了：主播主播，我也没得到最终结果啊，如果停止进位后前面还有0呢？操作前二进制后的数我们默认它不存在前导零，也就是最高位不可能是0，也就必定是1，取反后为0，得到的一定是一最高位为0的数，而0又可以舍去，因此合理
举个例子，110000~001111形如0001000可以转化为1000，也就是说最高位不可能是0
3.0.2.代码
int lowbit(int x)
{
return x&(-x);
}3.1.如何修改单点？
3.1.1.思路
更新一个点也要更新其祖上十八代，祖上十八代怎么推？
我们发现每向上一层\(lowbit\)值都增加\(1\),因此得到增加单点代码：
3.1.2 代码
修改单点：
void build(int x,int k){ for(int i=x;i
页:
[1]