累積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クラス(2021 ver)

// xor ver
struct AccXor{
  vector<ll> Ac;
  ll L;
  AccXor(){}
  AccXor(vector<ll> &A){
    L = A.size();
    Ac.resize(L+1);
    rep(i,L){
      Ac[i+1] = Ac[i] ^ A[i]; // 添字は1ずれる
    }
  }
  // sum of [a, b)
  ll sum(ll a, ll b){
    if(a<0){
      debug("halt [AccSum]a<0",a);exit(0);
      return -1;
    }
    if(b>L){
      debug("halt [AccSum]b>L-1",b,L-1);exit(0);
      return -1;
    }
    return Ac[b] ^ Ac[a];
  }
};

追記:XORの性質2

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

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

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

追記:和をXOR, ANDで書き換える