線段樹：懶傳播

在整數陣列（尺寸10^5）的操作是這樣的...線段樹：懶傳播

我該如何使用分段樹和惰性傳播？

2012-11-11 palatok

我會添加一條線索：XOR是關聯的。（A XOR X）XOR Y）與A XOR（X XOR Y）具有相同的結果。 –

@Patricia Shanahan，謝謝，但我知道。我的問題是要找出段的總和。 – palatok

您的問題是要查找也受到段上異或的數據段總和。如果您只有手術2，您將如何解決問題？ –

我會在每個節點上保留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

2012-11-12 20:24:49

我不明白這條線...... N [i] =（R-L + 1）-N [i]。爲什麼我會減去N [i]？ – palatok

反轉段中1的個數。假設我們有一個從3到7的分段和2個分段。這意味着用1比特來反轉這個數字，即所有的數字變成零，並且所有的零成爲一。 7-3 + 1-2 = 5 -2 = 3 –

你的答案是不正確的。你需要像這樣做一些懶惰的更新：http://p--np.blogspot.ro/2011/07/segment-tree.html。否則，如果你更新（1，n，x）和查詢（4,5），你將得到一個錯誤的答案，因爲更新只改變了根節點。

2013-02-24 14:17:17

回答