累積XOR, XORの性質

説明

  • 累積XORとは、累積和と同じように事前計算しておくことで範囲のXORをO(1)で求める方法のこと

XORの性質

  • a xor a = 0
  • a xor 0 = a
  • 上記を利用すると、A = a xor b xor c xor d xor e の値を持っていて c xor d xor e の値が知りたいときは A xor a xor b で求まる
  • (同じ値をかけてキャンセルできる)

code

// 累積XOR
struct AccXOR{
  VI Acc;
  AccXOR(VI& A){
    ll N = A.size();
    Acc.resize(N+1);
    rep(i, N){
      Acc[i+1] = Acc[i] ^ A[i];
    }
  }
  // 閉区間 [a, b]
  // A[a] ^ ... ^ A[b]を返す
  ll range(ll a, ll b){
    return Acc[b+1] ^ Acc[a];
  }
};

verified

https://yukicoder.me/submissions/408532

追記:XORの性質2

a⊕b = u
a + b = v
とする

a + b = a⊕b + 2 * (a&b)
よって
a&b = (v-u)/2 (ここでv, uのパリティは一致しているとする)
これにより+と&を変換できることがある

+ではなく&にすることでbitごとに考えられる
  • 再訪。この問題は手強いが学びも多い

f:id:peroon:20200823065207p:plain