翻转硬币的位操作

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

it代表一个完整的二叉树一些提示;节点1是根，节点k的子节点是2k和2k + 1。

完整的二叉树的叶子是硬币。内部节点是面向特定方式（低31位）的硬币数量和“翻转”标记（在符号位中）。如果翻转的市场清晰，则低31位计算节点子树中抬头硬币的数量，而如果翻转位被设置，则计数尾部硬币。

双方find和count在此使用的参数约定是i是被计数或翻转的节点，min是由该节点所表示的最低索引，并且max是最高的索引。在find和count中的前两个测试检查翻转/计数范围（由A和B定义）是否与节点i的范围不相交或包含节点i的范围。

你flip看到的是：

• 如果[A，B]是[最小值，最大值]脱节，什么也不做。
• 如果[A，B]包含[min，max]，则翻转翻转的标记。
• 否则，对两个孩子运行flip。一旦我们完成了这个，这里的不变量就会被破坏;通过在两个孩子中增加抬头硬币的数量来修复它。

你count看到的是：

• 如果[A，B]是[最小值，最大值]不相交，返回0
• 如果[A，B]包含[分钟，最大值]，返回该节点的计数。
• 否则，加起来我们孩子的数量。