2

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

实际的问题是有 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;
}

有人可以给我一些关于所有这些位操作背后的逻辑的提示吗

4

1 回答 1

4

it表示完全二叉树；节点 1 是根节点，节点 k 的子节点是 2k 和 2k+1。

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

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

你看到的flip是：

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

你看到的count是：

  • 如果 [A,B] 与 [min, max] 不相交，则返回 0。
  • 如果 [A,B] 包含 [min, max]，则返回此节点中的计数。
  • 否则，把我们孩子的人数加起来。
于 2013-06-02T11:02:12.533 回答