6

我发现很多人使用x += x & (-x),x -= x & (-x)来解决区间树问题（在实现数据结构如段树、二叉索引树等时）。

你能解释一下这个等式是什么意思吗？

例如：

void update(int m, int x) { 
    m++;
    while (m < N) {
        t[m] = t[m] + x;
        m += m & -m;
    }
}

int query(int m) { 
    int result= 0;
    m++;
    while (m > 0) {
        result = result + t[m];
        m -= m & -m;
    }
    return result;
}
4

4 回答 4

12

注意：这个答案（就像方法本身一样）假设有符号整数以二进制补码形式表示。

该表达式x & -x是一种快速但不可否认的奥秘方法，可以获取由最低设置位表示的值x（当所有其他位都清除时）。这有时被称为位的权重，在数值上等于 2 的位位置的幂（其中最低有效位是 position 0）。

该方法依赖于这样一个事实，即在和-的二进制（2s-comp）表示中只能设置一个位，这实际上是.x-xx

Quora上有很多关于它是如何工作的很好的解释，还有很多例子。

在您显示的updateand函数中，循环中query增加/减少m的量因此根据 (original) 中最低有效设置位的位置进行加权。whilem

随时要求进一步澄清和/或解释（但我不想复制/粘贴或解释我链接的太多讨论）。

于 2019-11-22T13:40:17.290 回答
4

正如@Adrian 已经就表达式的含义给出了一个很好的答案，我将用一个关于它如何工作的简单示例来补充它。

让我们考虑一下，我们x是一个 4 位数字（为简单起见）1100b。然后，

  1. x是0000 1100b（它的最低设置位在位置2（索引从左开始0）
  2. -x1111 0100b就像_0000 1100b + 1111 0100b = 0b
  3. -x & x结果0100b。唯一设置的位与最右边的位 in x-at 位置相同2。
于 2019-11-22T14:29:31.267 回答
3

另一种解释方式如下：

让X成为一个数字。然后X&-X代表the greatest power of 2 that divides X。

例子：

  1. 让X = 10，X&-X再给2。
  2. 让X = 7，X&-X再给1。
  3. 让X = 4，X&-X再给4。
于 2020-08-22T20:56:20.407 回答
2

在二进制索引树 ( Fenwick_tree ) 中，这些操作是更新和查询树。要查询树，您可以通过重置它最右边的设置位来查找元素的父级。要更新树，您不断向当前索引添加最低有效位以查找所有要更新的元素。

于 2020-06-08T19:42:52.673 回答