問題

xorは、

  • 結合性がある
  • 逆演算がある

つまり、

  • X ^ (Y ^ Z) = (X ^ Y) ^ Z
  • X^Y = ZならばX=Z^Y'なるY'が存在する（実はY自身）

という性質が成り立つ。

これの何が嬉しいかと言うと、配列A[1], .., A[N]の部分列和A[n] ^ .. ^ A[m]を計算するときに、 A[1] ^ .. ^ A[m] - (A[1] ^ .. ^ A[n-1])と計算できるということ。

A[n] ^ .. ^ A[m]という式は、配列の長さ\(N\)に対してO(\(N^2\))通り存在するが、それを計算するのに O(\(N\))のデータを持てば良い、というのが嬉しいところ。

ここまでは理解してたんだけど、途中で、A[i]を更新するにはどうしたら良いのか？というのを忘れていたので 回答できなかった。いつか勉強するときのためにメモしておく。