LC 3277. 查询子数组最大异或值

https://leetcode.cn/problems/maximum-xor-score-subarray-queries/description/

这题是挺有意思的一套题目，里面有几个点需要解决：

  1. 怎么计算这个xor值。题目里面计算xor的方法似乎是没有解析解的，但是观察可以发现其实不同范围的xor其实是可以共用的。对应代码里面就是 `pre` 这个部分
  2. 有了 `pre` 这个部分，我们可以很容易地映射到 `left`. 其中 `left[i][sz]` 表示以i为起点，长度是sz的范围内最大的xor值是多少。
  3. 第三个部分就是对left做前缀和求解，包括两种更新： `left[i][sz]` 更新为以i为起点，长度<=sz的范围内最大的xor值，然后再更新到 `[i, i+sz]` 这个范围内的最大xor值

我觉得这题可以做个图来做说明，但是感觉自己没有时间来做（还是不太愿意） 

class Solution:
    def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)

        pre = []
        t = nums
        pre.append(t)
        while len(t) != 1:
            t2 = []
            for i in range(1, len(t)):
                t2.append(t[i - 1] ^ t[i])
            pre.append(t2)
            t = t2

        left = [[0] * (n - i + 1) for i in range(n)]
        for i in range(n):
            sz = 1
            while i >= 0:
                left[i][sz] = pre[sz - 1][i]
                sz += 1
                i -= 1

        for i in range(n):
            for sz in range(1, len(left[i])):
                left[i][sz] = max(left[i][sz], left[i][sz - 1])

        # L[i][sz] = max(L[i][sz], .L[i+1][sz-1], L[i+2][sz-2]...)
        # L[i+1][sz-1] = max(L[i+1][sz-1], L[i+2][sz-2]...)
        for sz in range(1, n + 1):
            for i in range(n - sz + 1):
                if (i + 1) < n:
                    left[i][sz] = max(left[i][sz], left[i + 1][sz - 1])

        ans = []
        # 10 ** 5
        for q in queries:
            l, r = q
            ans.append(left[l][r - l + 1])
        return ans