------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP1.树状数组的应用场景
> 记笔记！
树状数组的询问在O(logN)级别
树状数组的更新在O(logN)级别
树状数组的用途是单点修改
什么意思呢，来看看吧！
树状数组的用途主要是前缀和改进优化
这是普通前缀和
1 2 3 4 5 6 7 8 9 a[i]a[i]a[i] 5 6 2 3 1 7 6 3 0 s[i]s[i]s[i] 5 11 13 16 17 24 30 33 33
若要修改，过程极其繁琐
> 如假如我要修改a[i]a[i]a[i]的第6项为9
A[I]修改
S[I]修改
可以看到，以上操作极其繁琐
os:一定会炸......
所以...
XP2.思路与讲解
树状数组主要是运用2进制拆分达到的
首先我们要明白2进制拆分
因为一个10进制数可以拆分成若干个2的n次幂数
如图
> 13=1+4+8
当然，其他数也可以
> 13=1+4+8
> 12=4+8
> 20=4+16
> 22=2+4+16
> 25=1+8+16
> ......
所以，我们可以通过这点优化前缀和
/如求S[13]
s[1]=a[1];
s[4]=a[1]+a[2]+a[3]+a[4];
s[8]=a[1]+a[2]+a[3]+a[4]+...+a[8];
s[13]=s[1]+s[4]+s[8];
XP3.求数并修改
那如何拆分呢？
1101 (13)
1101->
0001 (1)
1100->
0100 (4)
1000->
1000 (8)
0
1+4+8=13;
...
所以，我们发现，拆分数就是把2进制的最后一个1去掉
代码：x&(-x)
修改更加简单
若我要修改s[3]s[3]s[3]项，n=13n=13n=13，直接修改s[4]（a[1]+a[2]+a[3]+a[4]）s[4]（a[1]+a[2]+a[3]+a[4]）s[4]（a[1]+a[2]+a[3]+a[4]）, s[8]（a[1]+a[2]+a[3]+...+a[8]）s[8]（a[1]+a[2] +a[3]+...+a[8]）s[8]（a[1]+a[2]+a[3]+...+a[8]） 不修改s[1],s[2],s[16]...s[1],s[2],s[16]...s[1],s[2],s[16]...因为他们不在3~13范围内
XP4.实践与代码
可以知道我们需要一个update来进行单点修改，并同时向上递增修改,同时还需要一个sum求解，即l-r的和，根据上述所说，我们只需向下加和，比如l=13,r=3,先-8,再-2即可。更更更同时，还需有一个函数求x&(-x)
LOWBIT
UPDATE
我们要向上修改，在2进制中增加次幂即可 ，也就是+lowbit
x代表要修改的数，n是数组长,y是要改的数
SUM
我们要不断求和
eg:s[14]=s[8]+s[4]+s[2]eg:s[14]=s[8]+s[4]+s[2]eg:s[14]=s[8]+s[4]+s[2] 从14向下递减
也就是树状数组：
XP5.代码演示
> 原题出自luogu.P3374
> 枢纽帖
> 团队传送门
> 千万别点
