开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
chat
详细介绍一下树状数组
树状数组（Binary Indexed Tree，简称 BIT）是一种用于高效处理动态数据集的数值结构，特别适用于需要频繁进行前缀和查询和单点更新的场景。
树状数组通常用于求解序列的前缀和、区间和、频率统计等问题，尤其是在算法竞赛和计算几何中经常用到。
1. 树状数组的基本原理
树状数组通过利用二进制的性质，能够以对数时间复杂度（O(log n)）完成更新和查询操作。
具体来说，它将一个序列压缩成一个树形结构，以支持高效的前缀和查询与单点更新。
结构
树状数组的核心思想是：用一个辅助数组来记录当前元素和其之前元素的某些统计信息（通常是某个范围的和）。
- 假设我们有一个长度为
n的数组arr，目标是计算该数组的前缀和。 - 为了能高效地计算前缀和，我们建立一个与
arr同样大小的树状数组bit，通过特定的规则进行更新。
树状数组的结构实际上并不是一个树形数据结构，而是通过数组的下标和二进制操作来模拟树的结构。
数组更新和查询的核心思想
-
查询：对于任意位置
i，我们可以通过不断查找当前下标与其父节点之间的关系（即i -= lowbit(i)）来快速查询从数组开始到i的前缀和。其中，
lowbit(i)代表i的最低位的1所表示的值，具体实现为：lowbit(i) = i & (-i) -
更新：对于任意位置
i的更新，我们将变动的值更新到树状数组的相应节点上，并且由于树状数组的特性，这个更新需要沿着树形结构向上递归更新。
2. 树状数组的实现
假设我们有一个数组 arr，长度为 n，树状数组 bit 的长度同样为 n，bit 数组的下标从 1 开始（为了简化实现，不从 0 开始）。
树状数组的核心操作包括：
- 更新操作：将
arr[i]更新为一个新值x，我们需要调整bit数组，使其反映该变化。 - 查询操作：查询从
arr[1]到arr[i]的前缀和。
以下是一个简单的树状数组的实现（使用 Java 编写）：
public class FenwickTree {
private int[] bit; // 树状数组
private int n;
public FenwickTree(int n) {
this.n = n;
bit = new int[n + 1]; // 树状数组索引从1开始，大小为n+1
}
// 更新操作：在位置i增加值x
public void update(int i, int x) {
while (i <= n) {
bit[i] += x; // 更新当前节点的值
i += lowbit(i); // 移动到父节点
}
}
// 查询操作：查询前缀和[1, i]
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += bit[i]; // 累加当前节点的值
i -= lowbit(i); // 移动到父节点
}
return sum;
}
// 计算lowbit(i)
private int lowbit(int i) {
return i & (-i); // 低位的1所表示的值
}
public static void main(String[] args) {
FenwickTree fenwickTree = new FenwickTree(10);
fenwickTree.update(1, 3); // arr[1] += 3
fenwickTree.update(2, 5); // arr[2] += 5
System.out.println(fenwickTree.query(2)); // 输出前缀和[1, 2]，即3 + 5 = 8
fenwickTree.update(1, 2); // arr[1] += 2
System.out.println(fenwickTree.query(2)); // 输出前缀和[1, 2]，即5 + 5 = 10
}
}
3. 树状数组的时间复杂度
-
更新操作：每次更新会沿着树状数组向上更新，最多需要更新
O(log n)个节点。因此，更新操作的时间复杂度是O(log n)。 -
查询操作：查询前缀和时，最多需要访问
O(log n)个节点。因此，查询操作的时间复杂度也是O(log n)。
4. 应用场景
树状数组广泛应用于以下几种场景：
- 前缀和查询：比如求一个数组的前缀和或者区间和。
- 频率统计：在动态数据结构中，快速查询某个值出现的次数或者范围内出现的次数。
- 动态数据更新：可以用来处理动态变化的数据序列，特别是有增量更新需求的场景。
5. 树状数组的扩展
- 区间和：通过前缀和公式，可以用树状数组快速计算区间和：
sum[l, r] = query(r) - query(l-1) - 扩展到二维：树状数组可以扩展到二维，支持二维区域的前缀和查询和更新。
6. 与其他数据结构的比较
-
线段树：线段树也是一种支持区间查询和单点更新的数据结构。与树状数组相比，线段树的查询和更新操作的时间复杂度也是
O(log n)，但线段树的实现更复杂，且可以处理更多类型的查询（例如区间最大值、区间最小值等）。 -
平衡树（如 AVL 树、红黑树）：平衡树支持动态维护集合中的元素，并支持
O(log n)时间复杂度的插入、删除、查找等操作。相比之下，树状数组的更新和查询更为高效，但只能处理数值范围内的前缀和问题。
总结
树状数组是一个高效的数据结构，特别适用于频繁进行前缀和查询和单点更新的问题。
它通过巧妙地利用二进制位的低位来模拟树形结构，从而在 O(log n) 时间内完成更新和查询操作。
尽管树状数组不能处理更复杂的区间查询问题，但在特定场景下，它提供了一种既简洁又高效的解决方案。
实在无法理解这个位运算，结合具体的例子，一步步推导一下
理解树状数组中的位运算，特别是 lowbit(i) 的计算和应用，确实需要结合具体的例子一步步推导。
下面我们通过一个具体的例子，逐步解析树状数组的 lowbit(i) 以及它是如何帮助我们完成查询和更新操作的。
1. lowbit(i) 的含义
首先，我们来理解 lowbit(i)。 lowbit(i) 是一个二进制操作，表示数字 i 最低位的 1 所表示的值。具体来说，它的公式是：
lowbit(i) = i & (-i)
这里，& 是按位与运算，-i 是 i 的二进制补码（负数）。通过 lowbit(i) 我们可以获取 i 在二进制表示中最低位的 1 所对应的数字。
举个例子来说明：
假设 i = 6，我们来一步步推导：
i = 6的二进制表示是：0110。- 取
-i，即-6，我们首先需要求6的二进制补码：6的二进制补码是：1111 1010（假设为 8 位补码）。- 对
6取反得到：1000 0101，然后加 1 得到-6的二进制补码：1000 0110。
现在进行 & 运算：
i = 6的二进制是：0110。-i = -6的二进制是：1000 0110。- 按位与运算结果：
0110 & 1000 0110得到0000 0010，即 2。
所以，lowbit(6) = 2。
解释：
lowbit(6) 得到 2，意味着数字 6 中最低位的 1 所对应的数字就是 2。这对于树状数组的操作非常有用。
2. lowbit(i) 在树状数组中的应用
a. 用于查询
在树状数组中，查询前缀和时，我们要通过不断地跳到当前节点的父节点来实现。
假设我们要查询前缀和 arr[1] + arr[2] + ... + arr[i]，具体步骤如下：
- 计算当前节点
i的前缀和。 - 使用
lowbit(i)跳到父节点，继续查询直到i为 0。
举个具体的例子，假设树状数组的大小是 6，初始数组是 [0, 3, 2, 1, 5, 4]，我们要查询前缀和 arr[1] + arr[2] + ... + arr[4]。
- 查询
query(4)：- 计算
lowbit(4)：4的二进制表示是100，lowbit(4) = 4 & (-4) = 100 & 100 = 100，即 4。
- 累加当前
bit[4]（假设当前树状数组存的是前缀和，bit[4] = 5）。 - 然后通过
i -= lowbit(i)更新i = 4 - 4 = 0，查询结束。
- 计算
最终，query(4) 的结果是 bit[4] = 5。
b. 用于更新
树状数组中的更新操作也是通过 lowbit(i) 来实现的。我们在更新某个元素时，需要将其影响传递到树状数组中相关的节点。
举个具体的例子，假设我们要更新 arr[3]，将它的值增加 3（即 arr[3] += 3）。
i = 3，计算lowbit(3)：3的二进制表示是011，lowbit(3) = 3 & (-3) = 011 & 101 = 001，即 1。
- 更新
bit[3]，加上3（bit[3] += 3），然后根据lowbit(3)更新父节点：i = 3 + lowbit(3) = 3 + 1 = 4，继续更新bit[4]。
- 再继续更新
bit[4]，然后根据lowbit(4)更新到父节点，直到更新完所有相关节点。
这个过程会反映在树状数组中，确保我们可以根据更新后的数据正确计算前缀和。
3. 总结
lowbit(i)通过二进制操作找到数字i最低位的1对应的值，帮助树状数组在查询和更新时高效地向上或向下跳跃。- 通过不断利用
lowbit(i)更新树状数组，可以在O(log n)的时间内高效地完成查询和更新操作。 - 在查询时，通过计算
lowbit(i)反复减小i，直到到达根节点（即i = 0）；在更新时，通过计算lowbit(i)不断向上更新树状数组，确保树状数组中的值始终反映数组的最新状态。
通过这个过程，树状数组能高效地支持区间和查询与单点更新，使得它在处理动态数据时非常有用。
如何记忆呢？
理解树状数组中的位运算和其复杂流程确实可以让人感到困惑，但其实记忆和掌握这个概念并不一定需要靠死记硬背。更多的是通过对其基本原理和机制的理解，结合不断的练习和思考。这里有一些建议，帮助你更轻松地掌握和记忆树状数组：
1. 理解二进制的低位性质
树状数组中的 lowbit(i) 操作本质上是通过二进制操作找到数字中最低位的 1 所对应的值。我们可以通过理解二进制的基本规律来帮助自己理解为什么 lowbit(i) 能有效地帮助查询和更新：
- 二进制的特点：任何数字在二进制表示中，其最低位的
1表示该数字能被该位置的权重（2^k）所表示。通过lowbit(i)，你实际上是在查找一个权重范围，即在树状数组中指向的最小范围。
例如：
lowbit(4) = 4，说明4这个数字在二进制中有一个1在其第 2 位（2^2），因此影响的范围就是2^2 = 4。lowbit(6) = 2，说明6这个数字最低位的1在第 1 位（2^1），因此影响的范围是2^1 = 2。
2. 逐步理解流程，减少一次性负担
树状数组的实现本身的流程看起来可能有点复杂，但可以把它拆分成简单的小步骤。你不需要一次性记住所有细节，关键是理解每个步骤背后的原因。
例如，更新过程：
- 更新一个元素时，首先需要找到该元素影响的范围。通过
lowbit(i)，我们可以确定该元素影响的 “父节点”。 - 逐步向上更新树状数组，每次更新一个节点，然后再利用
lowbit(i)找到下一个需要更新的节点。
你可以通过画图来帮助记忆：画出一个树状数组的结构，标记每个节点的 lowbit(i)，并在图上逐步演示更新过程。通过直观的图形帮助理解这些步骤。
查询过程：
查询前缀和也是一个类似的过程：
- 从当前节点出发，通过
lowbit(i)确定需要访问的父节点。 - 一直向上走，直到访问到根节点（即
i = 0），累加过程中包含了从根到当前节点的所有前缀和。
3. 通过具体例子反复练习
实际的编程练习是加深理解最有效的方式。通过具体的例子来实现树状数组，可以帮助你理解每一个操作。你可以用一个简单的例子来实现树状数组，逐步调试每个操作。
例如，尝试编写一个小程序来实现树状数组的更新和查询，使用小数据量并观察每个步骤的变化。通过实际操作，你会逐渐发现每个操作的规律，从而理解如何利用 lowbit(i) 来实现这些功能。
4. 关联已知知识
如果你之前有其他数据结构的经验（例如栈、队列、链表、二分查找等），你可以将树状数组与这些已知的知识联系起来：
- 树状数组类似于“压缩”的树结构，但它并没有显式地构建树，而是利用数组下标和二进制来模拟树的层级关系。
- 在树状数组的操作中，
lowbit(i)就相当于在模拟树的父子关系，每次跳跃到上层节点时都减少了一个量级。
5. 总结和规律提取
树状数组的核心思想就是二进制分治。通过 lowbit(i) 实现快速的查询和更新。每次更新和查询时，利用 lowbit(i) 可以缩小范围，逐步解决问题。这个过程本质上就是一个“按位”操作的过程，它依赖于二进制表示的每一位的权重关系。
6. 持续练习和复习
为了加深记忆和理解，持续练习是必要的。你可以通过以下几种方式来加深对树状数组的掌握：
- 手写代码：自己手动实现树状数组，并进行调试。
- 解决问题：利用树状数组解决实际的算法题，例如区间和、频率统计等问题。
- 复习总结：定期回顾
lowbit(i)的定义和树状数组的流程，重新理解每个步骤的原理。
7. 思维导图或图示化
有些人通过图示来帮助理解和记忆。你可以画出树状数组的树形结构，每次更新或查询时标出每个节点的 lowbit(i)，看清楚树状数组是如何通过二进制的低位结构进行查询和更新的。
总结
- 不需要硬背树状数组的流程，理解 二进制的低位特性 和 树状数组的查询与更新思想 才是关键。
- 通过 具体的例子 和 图示化的步骤，逐步掌握每个操作的含义。
- 多做练习，逐步形成对树状数组操作的直观理解和记忆。
只要通过这种分步式的理解和练习，你会发现树状数组的复杂性会逐渐变得更加清晰，最终能够灵活地应用在算法中。
参考资料
https://leetcode.cn/problems/range-sum-query-mutable/
