algorithm - 抛硬币中的位操作

Question

我试图理解这段代码。我认为它使用了一些段树数据结构的变体，但我无法理解这段代码中的任何位操作。

实际问题是有N个硬币，我们有1个操作和1个查询

1. 在 [A,B] 范围内掷硬币
2. 分别求[A,B]范围内的头数。

.

 #define LEAVES (131072)
 #define MSB_V (0x80000000)
 #define MSB_P (31)

 int it[2 * LEAVES];
 int A, B;    //Query range

 void flip (int i, int min, int max)
 {
    if ((min > B) || (max <= A))
    {   }
    else if ((min >= A) && ((max-1) <= B))
    {   it[i] ^= MSB_V; }
    else
    {
        int l = 2 * i;
        int r = l + 1;
        int mid = (min + max) / 2;
        it[l] ^= it[i] & MSB_V;
        it[r] ^= it[i] & MSB_V;
        it[i] ^= MSB_V;
        flip(l, min, mid);
        flip(r, mid, max);
        it[i] = (it[l] >> MSB_P ? mid - min - (it[l] ^ MSB_V) : it[l]) +
                (it[r] >> MSB_P ? max - mid - (it[r] ^ MSB_V) : it[r]);
    }
}

int count (int i, int min, int max)
{
    int h;
    if ((min > B) || (max <= A))
    {   h = 0; }
    else if ((min >= A) && ((max-1) <= B))
    {   h = it[i] >> MSB_P ? max - min - (it[i] ^ MSB_V) : it[i]; }
    else
    {
        int l = 2 * i;
        int r = l + 1;
        int mid = (min + max) / 2;
        it[l] ^= it[i] & MSB_V;
        it[r] ^= it[i] & MSB_V;
        it[i] ^= MSB_V;
        it[i] = (it[l] >> MSB_P ? mid - min - (it[l] ^ MSB_V) : it[l]) +
                (it[r] >> MSB_P ? max - mid - (it[r] ^ MSB_V) : it[r]);
        h = count(l, min, mid) + count(r, mid, max);
    }
    return h;
}

谁能给我一些关于所有这些位操作背后的逻辑的提示

Answer 1

它代表一棵完全二叉树；节点1为根，节点k的子节点为2k和2k+1。

完全二叉树的叶子是硬币。内部节点是面向特定方向的硬币数量(在低 31 位中)和“翻转”标记(在符号位中)。如果翻转行情清空，则低31位统计该节点子树中单挑硬币的个数，如果设置翻转位，则统计反面硬币的个数。

这里find和count使用的参数约定是i是被计数或翻转的节点，min 是该节点表示的最低索引，max 是最高索引。 find 和 count 中的前两个测试检查翻转/计数范围(由 A 和 B 定义) ) 不相交或包含节点 i 的范围。

你在flip中看到的是:

• 如果 [A,B] 与 [min, max] 不相交，则什么也不做。
• 如果 [A,B] 包含 [min, max]，翻转翻转的标记。
• 否则，对两个 child 运行flip。一旦我们这样做了，这里的不变量就被破坏了；通过将两个 child 的单挑硬币数量相加来解决这个问题。

您在 count 中看到的是:

• 如果 [A,B] 与 [min, max] 不相交，则返回 0。
• 如果[A,B]包含[min,max]，返回该节点的计数。
• 否则，将我们 child 的计数加起来。