Fenwick Tree 中的点更新
Point Updates in Fenwick Tree
我很难理解将 LSB 添加到当前索引如何为我们提供包含给定点的下一个位置。
void update(int k, int x) {
while (k <= n) {
tree[k] += x;
k += k&-k; // adding LSB (least significant bit)
}
}
谁能给我解释一下或参考一些资源？我看到的所有资源都只是告诉您它有效，但没有解释原因。不过我知道查询是如何工作的。
谢谢。
P.S 我在这里看到了类似的问题，但我还是不明白，因为他们并没有真正解释。
Fenwick Tree 数据结构可能很难从根本上掌握，但是一旦你理解了底层数学，你就应该精通它。因此，我将尝试解释关于 Fenwick Trees.[=26 的所有 hows 和 whys =]
分域树是基于数组索引的二进制表示
首先，您应该牢记的是：
Idea of the Fenwick Tree is based on a fact, that each integer number can be represented as a Binary Number, i.e. as a sum of different powers of 2, and that representation will be unique; e.g. integer number 14 can be represented as 23+22+21.
请注意，“different”是此定义中的重要关键字，因此您不应将 14 表示为 23+21+21+21.
分域树的填充方式
我这里就不实现Fenwick Tree的种群算法（你说的，树是怎么种群的，你懂的，除此之外，与题目无关）；但是，我要强调的是，Fenwick Tree [大部分] 是通过数组实现的，在某种程度上，fenwick-tree[= 中的每个插槽155=]数组，保存一个值，是原数组范围之和，其中：
- 该范围内的右索引是 k 本身（此插槽是右边界）；
- 该范围内的元素数量是该索引的 sum-of-the-powers-of-two 表示中的最小 addend（因此，您应该计算 个元素的数量，从右到左，以获得有问题的范围。
P。 S. 如果 Fenwick Tree 在索引 24 处存储了一些 n 值，这意味着 原始数组，将是n.
Q：为什么17是左界？
A：因为，24是24+23，而最小加数 从这个表达式是 23 = 8。现在，根据上面给出的定义，[=84= 中索引 24 处的元素的范围加起来]Fenwick Tree 数组，将包含 8 个元素，如果右边界恰好位于索引 24 本身，则从右到左的 8 个连续元素将使我们到达左边界，即索引 17 ;因此，我们在 [17, 24] 范围内有 8 个元素，索引 24 处的值将是 n，这是 [17, 24] 范围内元素的总和。
这张图片甚至可以清楚地说明我上面写的内容：
重要提示：
将整数表示为 2 的不同次幂之和，源于 二进制数字系统.
的原理
例如1011可以写成23+21+20.
leftmost column, in the binary representation, constitutes 2 to the power of 3, and the right most column constitutes 2 to the power of 0. In the binary representation, powers of 2 increase by 1 per each step from rightmost column to the left.
如果你了解二进制数字系统，你应该明白，当将一些数 N 表示为不同幂的总和时两个中的最小数字，即该总和中的最小数字，与 N 的二进制表示中从最低有效位 (LSB) 开始并以该二进制最右边的数字结束的部分相同表示，这也与 2 的 indexOf(LSB)-1 次方相同（如果您从右侧开始用 1 索引二进制数）或 indexOf(LSB)（如果你用 0 索引你的数字）。
这一切带来了什么？
更快的范围查询
看看范围查询在分域树中是如何工作的。
我希望你明白我们需要前缀和来进行范围查询。
为了计算 original[0, index] 的 前缀总和 ，而不是迭代整个数组，您现在只需在相应的 中级联Fenwick Tree，从那个 index，你 不断地从那些索引 的值中删除 LSB，同时你不断地总结值在所有这些索引处（它们是原始数组范围的总和）。
这看起来像：
int prefixSum(int index) {
int sum = 0;
while(index!=0) {
sum+=fenwickTree[index];
index = index - LSB(index);
}
return sum;
}
问：为什么这样做有效？
A：我认为现在应该很明显了，但如果仍然不明显 - 那么请密切注意 为什么我们删除 LSB(index) .我们这样做是因为在计算 前缀和 时将 fenwickTree[index] 添加到当前总和之后，正如我们在上面已经解释过的那样，下一个槽存储原始数据的另一片数组区间，会在index = index - LSB(index)，因为在Fenwick Tree中，index k存储了长度[2LSBIndexOf(toBinary(k))-1,k]
因此，根据我们刚才展示的（级联、求和和 index-LSB(index)），使用 Fenwick Tree，索引 11 的前缀和（对于例如），将被计算为：
prefixSum = fenwickTree[11] + fenwickTree[10] + fenwickTree[8]
因为：
fenwickTree[11] 存储 original[11] 的总和（奇数索引仅存储那些值指数);fenwickTree[10] 存储 original[9,10] 的总和；fenwickTree[8] 存储 original[1, 8].
你基本上有 3 个切片来总结：[1,8]、[9,10] 和 [11]。
更快的积分更新
查看点更新在分域树中是如何工作的。
我认为，Point Update 工作的原因和方式现在很明显了——就 LSB 而言，它是范围查询的相反操作 - 您将添加 LSB（索引）而不是删除 LSB（索引），现在向上级联到索引并更新 Fenwick Tree.[=26 中的相应索引=]
例如，如果我们想在索引 9 处添加一个值，您必须找出负责该索引的所有插槽，并且必须更新它们。我们必须从索引 9 元素的 LSB 开始获取数字，我们必须将它添加到索引 9 处的值。我们必须不断重复此操作，直到到达 LSB 是该索引本身处的数字的位置。就是这样。
void update(int i, int x) {
while (i <= n) {
fenwickTree[i] += x;
i += LSB(i); //this will give you the next slot which is used as an addend
}
}
我真的希望这对您有所帮助并阐明您的理解。
我很难理解将 LSB 添加到当前索引如何为我们提供包含给定点的下一个位置。
void update(int k, int x) {
while (k <= n) {
tree[k] += x;
k += k&-k; // adding LSB (least significant bit)
}
}
谁能给我解释一下或参考一些资源？我看到的所有资源都只是告诉您它有效，但没有解释原因。不过我知道查询是如何工作的。
谢谢。
P.S 我在这里看到了类似的问题，但我还是不明白，因为他们并没有真正解释。
Fenwick Tree 数据结构可能很难从根本上掌握，但是一旦你理解了底层数学，你就应该精通它。因此，我将尝试解释关于 Fenwick Trees.[=26 的所有 hows 和 whys =]
分域树是基于数组索引的二进制表示
首先，您应该牢记的是：
Idea of the Fenwick Tree is based on a fact, that each integer number can be represented as a Binary Number, i.e. as a sum of different powers of 2, and that representation will be unique; e.g. integer number 14 can be represented as 23+22+21.
请注意，“different”是此定义中的重要关键字，因此您不应将 14 表示为 23+21+21+21.
分域树的填充方式
我这里就不实现Fenwick Tree的种群算法（你说的，树是怎么种群的，你懂的，除此之外，与题目无关）；但是，我要强调的是，Fenwick Tree [大部分] 是通过数组实现的，在某种程度上，fenwick-tree[= 中的每个插槽155=]数组，保存一个值，是原数组范围之和，其中：
- 该范围内的右索引是 k 本身（此插槽是右边界）；
- 该范围内的元素数量是该索引的 sum-of-the-powers-of-two 表示中的最小 addend（因此，您应该计算 个元素的数量，从右到左，以获得有问题的范围。
P。 S. 如果 Fenwick Tree 在索引 24 处存储了一些 n 值，这意味着 原始数组，将是n.
Q：为什么17是左界？
A：因为，24是24+23，而最小加数 从这个表达式是 23 = 8。现在，根据上面给出的定义，[=84= 中索引 24 处的元素的范围加起来]Fenwick Tree 数组，将包含 8 个元素，如果右边界恰好位于索引 24 本身，则从右到左的 8 个连续元素将使我们到达左边界，即索引 17 ;因此，我们在 [17, 24] 范围内有 8 个元素，索引 24 处的值将是 n，这是 [17, 24] 范围内元素的总和。
这张图片甚至可以清楚地说明我上面写的内容：
重要提示：
将整数表示为 2 的不同次幂之和，源于 二进制数字系统.
的原理例如1011可以写成23+21+20.
leftmost column, in the binary representation, constitutes 2 to the power of 3, and the right most column constitutes 2 to the power of 0. In the binary representation, powers of 2 increase by 1 per each step from rightmost column to the left.
如果你了解二进制数字系统，你应该明白，当将一些数 N 表示为不同幂的总和时两个中的最小数字，即该总和中的最小数字，与 N 的二进制表示中从最低有效位 (LSB) 开始并以该二进制最右边的数字结束的部分相同表示，这也与 2 的 indexOf(LSB)-1 次方相同（如果您从右侧开始用 1 索引二进制数）或 indexOf(LSB)（如果你用 0 索引你的数字）。
这一切带来了什么？
更快的范围查询
看看范围查询在分域树中是如何工作的。
我希望你明白我们需要前缀和来进行范围查询。
为了计算 original[0, index] 的 前缀总和 ，而不是迭代整个数组，您现在只需在相应的 中级联Fenwick Tree，从那个 index，你 不断地从那些索引 的值中删除 LSB，同时你不断地总结值在所有这些索引处（它们是原始数组范围的总和）。
这看起来像：
int prefixSum(int index) {
int sum = 0;
while(index!=0) {
sum+=fenwickTree[index];
index = index - LSB(index);
}
return sum;
}
问：为什么这样做有效？
A：我认为现在应该很明显了，但如果仍然不明显 - 那么请密切注意 为什么我们删除 LSB(index) .我们这样做是因为在计算 前缀和 时将 fenwickTree[index] 添加到当前总和之后，正如我们在上面已经解释过的那样，下一个槽存储原始数据的另一片数组区间，会在index = index - LSB(index)，因为在Fenwick Tree中，index k存储了长度[2LSBIndexOf(toBinary(k))-1,k]
因此，根据我们刚才展示的（级联、求和和 index-LSB(index)），使用 Fenwick Tree，索引 11 的前缀和（对于例如），将被计算为：
prefixSum = fenwickTree[11] + fenwickTree[10] + fenwickTree[8]
因为：
fenwickTree[11]存储original[11]的总和（奇数索引仅存储那些值指数);fenwickTree[10]存储original[9,10]的总和；fenwickTree[8]存储original[1, 8]. 的总和
你基本上有 3 个切片来总结：[1,8]、[9,10] 和 [11]。
更快的积分更新
查看点更新在分域树中是如何工作的。
我认为，Point Update 工作的原因和方式现在很明显了——就 LSB 而言，它是范围查询的相反操作 - 您将添加 LSB（索引）而不是删除 LSB（索引），现在向上级联到索引并更新 Fenwick Tree.[=26 中的相应索引=]
例如，如果我们想在索引 9 处添加一个值，您必须找出负责该索引的所有插槽，并且必须更新它们。我们必须从索引 9 元素的 LSB 开始获取数字，我们必须将它添加到索引 9 处的值。我们必须不断重复此操作，直到到达 LSB 是该索引本身处的数字的位置。就是这样。
void update(int i, int x) {
while (i <= n) {
fenwickTree[i] += x;
i += LSB(i); //this will give you the next slot which is used as an addend
}
}
我真的希望这对您有所帮助并阐明您的理解。