algorithm - セグメントツリー：遅延伝播

Question

整数配列（サイズ10 ^ 5）では、操作は次のようになります。

1. インデックスLからRまでのすべての要素に対して特定の数値Xでビット単位のxor演算を実行します
2. インデックスLからRまでの数値の合計を求めます。

セグメントツリーとレイジープロパゲーションでそれを行うにはどうすればよいですか？

Answer 1

各ノードで、子ノードのバイナリ表現の各位置にいくつの整数があるかを示す32個の整数を保持します。

セグメントノードをXORするには、各位置にあるノードの数を反転するだけです（Xのビット1ごとに）。

for i in range(32):
    if X&(1<<i):
        N[i] = (R-L+1)-N[i]. 

合計を計算するには、

s = 0
for i in range(32):
    s |= ((N[i]+carry)%2) << i
    carry = (N[i]+carry)/2

Answer 2

あなたの答えは正しくありません。あなたはここのようなある種の怠惰な更新をする必要があります：http：//p--np.blogspot.ro/2011/07/segment-tree.html。それ以外の場合、update（1、n、x）とquery（4,5）を実行すると、更新によってルートノードのみが変更されたため、間違った答えが返されます。