页面历史记录

...

原数组是a1~a8，数组状数组是c1~c8，它们拥有的元素个数完全一样，并且都从下标1开始存储元素。

分析树数组和原数组的关系，列出对应的二进制：

这里首先可以推导出这里首先介绍如何推导出cx管理的元素个数，推导公式如下：

int lowbit(int x) {
    return x & -x;
}

这个公式可以返回x的二进制右侧第一个非0的部分，比如：0001，0010，0011，0100，0101，0110，0111，1000。

推导出元素个数后，就可以知道cx管理的元素范围为[x-lowbit(x)+1, x]。，比如c8管理的元素范围是[1, 8]。

根据上面的二进制关系，同样可以推导出原数组根据上面的二进制关系，同样可以推导出原数组元素ax归哪些树状数组节点管理，比如从上面的例子可知，a1归c1, c2, c4, c8管理，那么在更新a1的值时，就要同步更新c1, c2, c4, c8 的值。

...

void update(int k, int val) {
    for(int i = k; i <= n; i += lowbit(i); { // 推导a[k]归哪些c[i]管理
        c[i] += val;
    }
}

代入上面的表格进行验证即可。

...

int getsum(int x) {
    int ans = 0;
    while(x >= 1) {
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}

同样代入上面的表格进行验证即可。

最后是如何建立树状数组，示例代码如下，这里在每确定一个c[i]时，都会更新一次c[i]的直接父结点，由于父结点的值只来自于子结点求和，所以建树的时间复杂度为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) c[j] += c[i];
	}
}

示例例题：

• 307. 区域和检索 - 数组可修改 - 力扣（LeetCode）
  • 思路：考虑使用树状数组，有以下注意点：
    1.保存原数组
    2.数组下标从0开始
    3.传入的val要转化成diff = val-nums[i]
    4.求区间和转化成求两次前缀和再作差