XOR prefix sum C++ python解Leetcode 1829 Maximum XOR for Each Query

XOR prefixsum CPP python解Leetcode 1829  Maximum XOR for Each Query

其實這裡考慮的是元素個數為2^maximumBit的交換群，運算子為XOR。

[Python code請進]

bitwise XOR has the perfect algebaic properties, e.g. x^x=0, x^y=y^x, x^(~x)=0

x^k=y implies x^k^x=k=y^x

[codes on Leetcode]https://leetcode.com/problems/maximum-xor-for-each-query/solutions/6021105/prefix-sum-1-pass-vs-partial-sum-beats-100/

[Prefix sum playlist]https://www.youtube.com/watch?v=1kA_aZHewmU&list=PLYRlUBnWnd5LkYN-5ptHDrtPXOuHm9uSq

[bit/ bit mask playlist]https://www.youtube.com/watch?v=Hw1fnQA8Nk8&list=PLYRlUBnWnd5K8FlzJ6tOswqQcsk7R1Duh

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        #bitwise XOR has the perfect algebaic properties, e.g. x^x=0, x^y=y^x, x^(~x)=0
        #x^k=y=> x^k^x=k=y^x
        mask, n=(2**maximumBit-1, len(nums)
        ans=[0]*n
        ans[-1]=nums[0]^mask
        for i in range(1, n):
            ans[~i]^=(ans[n-i]^nums[i])
        return ans