<p>You are given an array <code>nums</code> of <code>n</code> integers, and a 2D integer array <code>queries</code> of size <code>q</code>, where <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code>.</p>

<p>For each query, you must find the <strong>maximum XOR score</strong> of any <span data-keyword="subarray">subarray</span> of <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.</p>

<p>The <strong>XOR score</strong> of an array <code>a</code> is found by repeatedly applying the following operations on <code>a</code> so that only one element remains, that is the <strong>score</strong>:</p>

<ul>
	<li>Simultaneously replace <code>a[i]</code> with <code>a[i] XOR a[i + 1]</code> for all indices <code>i</code> except the last one.</li>
	<li>Remove the last element of <code>a</code>.</li>
</ul>

<p>Return an array <code>answer</code> of size <code>q</code> where <code>answer[i]</code> is the answer to query <code>i</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[12,60,60]</span></p>

<p><strong>Explanation:</strong></p>

<p>In the first query, <code>nums[0..2]</code> has 6 subarrays <code>[2]</code>, <code>[8]</code>, <code>[4]</code>, <code>[2, 8]</code>, <code>[8, 4]</code>, and <code>[2, 8, 4]</code> each with a respective XOR score of 2, 8, 4, 10, 12, and 6. The answer for the query is 12, the largest of all XOR scores.</p>

<p>In the second query, the subarray of <code>nums[1..4]</code> with the largest XOR score is <code>nums[1..4]</code> with a score of 60.</p>

<p>In the third query, the subarray of <code>nums[0..5]</code> with the largest XOR score is <code>nums[1..4]</code> with a score of 60.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[7,14,11,14,5]</span></p>

<p><strong>Explanation:</strong></p>

<table height="70" width="472">
	<thead>
		<tr>
			<th>Index</th>
			<th>nums[l<sub>i</sub>..r<sub>i</sub>]</th>
			<th>Maximum XOR Score Subarray</th>
			<th>Maximum Subarray XOR Score</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>0</td>
			<td>[0, 7, 3, 2]</td>
			<td>[7]</td>
			<td>7</td>
		</tr>
		<tr>
			<td>1</td>
			<td>[7, 3, 2, 8, 5]</td>
			<td>[7, 3, 2, 8]</td>
			<td>14</td>
		</tr>
		<tr>
			<td>2</td>
			<td>[3, 2, 8]</td>
			<td>[3, 2, 8]</td>
			<td>11</td>
		</tr>
		<tr>
			<td>3</td>
			<td>[3, 2, 8, 5, 1]</td>
			<td>[2, 8, 5, 1]</td>
			<td>14</td>
		</tr>
		<tr>
			<td>4</td>
			<td>[5, 1]</td>
			<td>[5]</td>
			<td>5</td>
		</tr>
	</tbody>
</table>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 2000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>1 &lt;= q == queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length == 2 </code></li>
	<li><code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code></li>
	<li><code>0 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt;= n - 1</code></li>
</ul>

from math import ceil, log2
from collections import defaultdict

class segment_tree:
    # merge(left, right): function used to merge the two halves
    # basef(value): function applied on individual values
    # basev: identity for merge function, merger(value, basev) = value
    # update(node_value, old, new): function to update the nodes
    def __init__(self, array, merge=lambda x,y:x+y, basef=lambda x:x, basev = 0):
        self.merge = merge
        self.basef = basef
        self.basev = basev
        self.n = len(array)
        self.array = array
        self.tree = [0] * ( 2**ceil(log2(len(array))+1) - 1 )
        self.build(array)
    
    def __str__(self):
        return ' '.join([str(x) for x in self.tree])

    def _build_util(self, l, r, i, a):
        if(l==r):
            self.tree[i] = self.basef(a[l])
            return self.tree[i]
        mid = (l+r)//2
        self.tree[i] = self.merge(self._build_util(l,mid, 2*i+1, a), self._build_util(mid+1, r, 2*i+2, a))
        return self.tree[i]

    def build(self, a):
        self._build_util(0, len(a)-1, 0, a)

    def _query_util(self, i, ln, rn, l, r):
        if ln>=l and rn<=r:
            return self.tree[i]
        if ln>r or rn<l:
            return self.basev
        return self.merge( self._query_util( 2*i+1, ln, (ln+rn)//2, l, r ), self._query_util( 2*i+2, (ln+rn)//2+1, rn, l, r ) )

    def query(self, l, r):
        return self._query_util( 0, 0, self.n-1, l, r )

    def _update_util(self, i, ln, rn, x, v):
        if x>=ln and x<=rn:
            if ln != rn:
                self._update_util( 2*i+1, ln, (ln+rn)//2, x, v )
                self._update_util( 2*i+2, (ln+rn)//2 + 1, rn, x, v )
                self.tree[i] = self.merge(self.tree[2*i+1], self.tree[2*i+2])
            else:
                self.tree[i] = self.basef(v)

    def update(self, x, v):
        self._update_util( 0, 0, self.n-1, x, v )   
        self.array[x] =v         

class Solution:
    def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        scores = [[0] * len(nums) for _ in range(len(nums))]
        for i in range(len(nums)):
            scores[i][i] = nums[i]
        for l in range(1, len(nums)):
            for i in range(len(nums) - l):
                scores[i][i + l] = scores[i][i + l - 1] ^ scores[i + 1][i + l]
        qmap = defaultdict(list)
        qend = [[] for _ in range(len(nums))]
        for i in range(len(queries)):
            qmap[tuple(queries[i])].append(i)
            qend[queries[i][1]].append(queries[i][0])
        curr = nums[:]
        ans = [0] * len(queries)
        for i in range(len(nums)):
            for j in range(i):
                curr[j] = max(curr[j], scores[j][i])
            if len(qend[i]) == 0:
                continue
            suffix = [-float('inf')]
            for j in range(i, -1, -1):
                suffix.append(max(suffix[-1], curr[j]))
            # print(suffix)
            for q in qend[i]:
                for index in qmap[(q, i)]:
                    ans[index] = suffix[i + 1 - q]
                # print(ans)
        return ans
155819