...
这个公式可以返回x的二进制右侧第一个非0的部分，比如：0001，0010，0011，0100，0101，0110，0111，1000。
| 提示 |
|---|
lowbit(x)的求法是x各位取反再加1，再与x本身进行与操作，比如i=20，其二进制表示为10100，取反之后为01011，加1之后为01100，再与20本身进行与操作，结果为01100&10100，得到结果为100。
而x各位取反再加1，刚好就是-x的补码表示，所以lowbit(x) = x & -x。 |
推导出元素个数后，就可以知道cx管理的元素范围为[x-lowbit(x)+1, x]。，比如c8管理的元素范围是[1, 8]。
...
| 代码块 |
|---|
int getsum(int x) {
int ans = 0;
while(x >= 1) {
ans += c[x];
x -= lowbit(x);
}
return ans;
} |
同样代入上面的表格进行验证即可。
最后是如何建立树状数组，示例代码如下，这时在每确定一个最后是如何建立树状数组，示例代码如下，这里在每确定一个c[i]时，都会更新一次c[i]的直接父结点，则于父结点的值只来自于子结点求和，所以建树的时间复杂度为O的直接父结点，由于父结点的值只来自于子结点求和，所以建树的时间复杂度为O(n)：
| 代码块 |
|---|
#define MAXN 1005
int a[MAXN];
int c[MAXN];
int n;
void init() {
for(int i = 1; i <= n; i++) {
c[i] += a[i];
int j = i + lowbit(i);
if(j <= n) tc[j] += tc[i];
}
} |
示例例题：
- 307. 区域和检索 - 数组可修改 - 力扣（LeetCode）
- 思路：考虑使用树状数组，有以下注意点：
1.保存原数组
2.数组下标从0开始
3.传入的val要转化成diff = val-nums[i]
4.求区间和转化成求两次前缀和再作差
- 思路：考虑使用树状数组，有以下注意点：