树状数组（Binary Indexed Tree, BIT）是一种高效的数据结构，主要用于实现单点更新和区间查询。其核心思想是通过二进制分解将数组元素映射到树状结构中，从而实现高效操作。以下是树状数组与二进制相关的关键内容：

一、lowbit函数

lowbit（x）是树状数组的核心操作，用于获取x的二进制表示中最低位的1所对应的值。其计算公式为：

$$ text{lowbit}(x) = x & -x $$

例如：

$text{lowbit}（110_{（2）}） = 10_{（2）}$

$text{lowbit}（23） = 2_{（2）}$ [因为23的二进制为10111，最低位1后有4个0，$2^4=16$]

二、树状数组的区间划分

树状数组通过二进制分解将数组划分为多个小区间，每个节点管理一个区间。对于位置x，其管理的区间为：

$$ [y, x] $$

其中：

$y = x - text{lowbit}（x）$

$x$为当前节点位置。

例如，对于位置10（二进制1010），

$text{lowbit}（10） = 2$

$y = 10 - 2 = 8$

因此，节点10管理区间[8, 10]。

三、单点更新操作

单点更新通过差分数组实现，具体步骤为：

1. 在原数组位置x增加值c：

$$ text{add}(x, c) $$

2. 更新所有包含x的父节点：

从x开始，每次加上$text{lowbit}（i）$，直到超过数组长度n：

$$ i = x $$

$$ text{while}(i leq n) { text{tr}[i] += c; i += text{lowbit}(i) } $$

例如，更新位置5增加3：

- $i=5$，$text{tr} += 3$

- $i=7$，$text{tr} += 3$

- $i=8$，$text{tr} += 3$ [停止条件：$i=9$时，$text{lowbit}（9）=1$，$i+1=10$超过n]

四、区间查询操作

区间查询通过前缀和实现，例如查询[1, x]的和：

$$ text{sum}(x) = sum_{i=1}^{x} a_i $$

计算过程为：

1. 初始化结果res为0：

$$ text{res} = 0 $$

2. 从x开始，每次减去$text{lowbit}（i）$，累加对应节点值：

$$ i = x $$

$$ text{while}(i >

0) { text{res} += text{tr}[i]; i -= text{lowbit}(i) } $$

例如，查询[1, 5]的和：

- $i=5$，$text{res} += text{tr} = 3$

- $i=3$，$text{tr} += 2$ [差分数组前缀和为5]

- $i=2$，$text{tr} += 1$ [差分数组前缀和为4]

- 最终结果为5

五、差分数组与树状数组的结合

差分数组是树状数组进行区间修改的优化手段。对于区间修改操作（如[L, R]增加C），只需在差分数组的L位置增加C，在R+1位置减少C，再通过两次单点更新即可完成。

总结

树状数组通过二进制分解和位运算实现高效的单点更新与区间查询，其核心在于lowbit函数和差分数组的结合。这种设计使得树状数组在时间复杂度上优于线段树（均为O（log n）），但空间复杂度较低。