树状数组

# 这只是一个树状数组的笔记而已HHHH 下面开始正文 其实现在我也没太弄懂它的原理，只是... XD 首先，我们需要把一个数转成二进制，然后找它最低位的1 怎么找呢？ 我们知道，负数在计算机中的存储方式是将一个数按位取反，然后再＋1 比如说： ``` 5 ``` 可以转换为 ``` (前面省略)0000000101 ``` 而 ``` -5 ``` 则可以存储为 ``` （前面省略）1111111010 + 1 = (前面省略)1111111011 ``` 而如果把5 & -5会怎么样呢？我们来模拟一下： ``` 0000000101 &1111111011 ------------ 0000000001 = 1 ``` 相似地，我们可以再举几个例子： ``` 7=0000000111; -7=1111111000+1=1111111001 7 & -7 = 0000000111 &1111111001 ------------ 0000000001=1 ``` ``` 12 & -12 = 00000001100 &11111110100 ------------- 00000000100=4 ``` 因此，我们可以发现：如果把一个数按位与上它的负数，就可以得到它最后一位1加上后面一串0的确切值啦！ ### 注意：这样返回的并不是最后一位1的位置，而是最后一个1后面填上一串0然后转成10进制之后的值。 所以说，我们可以写出如下代码来计算某个数最后一位1再填上一串0的数 ```cpp int lowbit(int x) { return x & -x; } ``` 下面，我们还需要做的就是单点添加和区间求和问题 #### 单点添加 ```cpp void add(int pos,int num) { while(pos <= n) { c[pos] += num; pos += lowbit(pos); } } ``` #### 区间求和 ```cpp int sum(int q) { int ans = 0; while(q) { ans += c[q]; q -= lowbit(q); } return ans; } ``` 当然，如果我们要把某个区间全都修改成某一个值该怎么办呢？ （思考） 其实，我们可以做的是把区间开始的点加上某个值，再在区间结束的地方减去某个值就行了qwq （这就是传说中的~~查分~~差分思想） 比如说像这样： ```cpp scanf("%d%d%d",&o,&p,&q);//o是区间起点，p是区间终点，q是要加上的值 add(o,q);//在o位置加上q add(p + 1,-q);//在p + 1位置减去q ``` 好了，树状数组的基本操作大概就是这样。有了树状数组，你就可以更快速地进行关于普通数组的批量~~操作♂~~啦（滑稽）