树状数组
- 树状数组引入：
给出一个数组A：A[1]~A[10000];
给出多个查询区间[L~R],求区间和;
L R
E1: 3 - 10000
E2: 5 - 9999
直接使用原数组时间复杂度肯定很高
引入前缀和
S[L]=A[1]+A[2]+…+A[L];
S[R]=A[1]+A[2]+...+A[R];
求区间和就好求了许多
E：A[L]~A[R]的和
= S[R]-S[L-1];
看起来挺好，用起来很是方便，可是它也有不太好的地方，如果有修改的话，每次修改就要把修改数及其之后的前缀和全部修改，那么针对需要修改的题来说这个效率又变得很低
|
|
|
X |
Lowbit |
|
十进制 |
二进制 |
（末尾0个数） |
子叶数 |
|
C[4] |
100 | 2 | 2^2 |
|
C[3] |
011 | 0 | 2^0 |
|
C[2] |
010 | 1 | 2^1 |
|
C[1] |
001 | 0 | 2^0 |
Lowbit：其实是求一个非负整数n在二进制表示下“最低位1和其后边0”构成的数值。
C[i]代表从A[i-2^x+1]+…+A[i]
Lowbit(x)
Return x&(-x);
求解 E：10101000 经过Lowbit计算之后得到00001000
（取反：一个数的二进制表示法下从左向右数遇到的第一个1和所有0保持不变，向右的其余数字一次取反）
（按位与运算：1&1=1 1&0=0 0&1=0 0&0=0 ）
设n>0,n的第k位为1，0~k-1位都是0，取反之后1右边的数字取反，0到k位保持不变。按位与运算之后0到k位仍然不变
以上是关于Lowbit（）函数的解释，关于求和和更新的函数贴个解析：