範圍異或使用BIT或樹狀數組

Question

對於整數的給定陣列總和，我們要計算XORed總和withing給定範圍[L, R]，通過XORed總和我的意思是Σ(Arr[i]^p)其中i:[L,R]和p是一些數。在計算XORed總和時，可以輕鬆完成此操作，直到數組中的每個i-th元素爲止。現在問題發生在p頻繁更改時。並重新計算XORed總和，直到每個i-th元素在這種情況下似乎都不是理想的解決方案。我想這可以使用fenwick tree或BIT來完成。但我無法弄清楚如何進行fenwick樹或BIT。任何幫助，將不勝感激。

Answer 1

我們可以獨立解決每個位的問題。

我們假設我們要計算第k位對答案的貢獻。如果設置爲p，則答案是該範圍內元素的數量，該位的值等於零（否則，對於該位等於1的元素，它是相同的）。

如何有效地計數這些元素的數量？我們可以爲每一位構建一個前綴總和數組。這樣，我們就可以在一定的時間範圍內獲得有或沒有給定位的元素的數量。