Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the XOR of elements from Li to Ri (that is, arr[Li] xor arr[Li+1] xor ... xor arr[Ri] ). Return an array containing the result for the given queries.
 
Example 1:
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

 
Constraints:

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Range queries
Skill types: Bit manipulation

Data structures

Range queries

Starter code:
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        

Solutions:
from itertools import accumulate

class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xors = [0]
		for a in arr:
			xors.append(a ^ xors[-1])
		return [xors[i] ^ xors[j + 1] for (i, j) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		prefix_xor = [0] * n
		prefix_xor[0] = arr[0]
		for i in range(1, n):
			prefix_xor[i] = prefix_xor[i - 1] ^ arr[i]
		ret = []
		for (start, end) in queries:
			if start == 0:
				ret.append(prefix_xor[end])
			else:
				ret.append(prefix_xor[start - 1] ^ prefix_xor[end])
		return ret


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = []
		curr = 0
		for n in arr:
			curr ^= n
			prefix.append(curr)
		res = []
		for (l, r) in queries:
			if l == 0:
				res.append(prefix[r])
			else:
				res.append(prefix[r] ^ prefix[l - 1])
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		result = []
		prefixArr = [0] * len(arr)
		prefixArr[0] = arr[0]
		for i in range(1, len(arr)):
			prefixArr[i] = prefixArr[i - 1] ^ arr[i]
		for j in range(len(queries)):
			start = queries[j][0]
			end = queries[j][1]
			if start == 0:
				result.append(prefixArr[end])
			else:
				result.append(prefixArr[start - 1] ^ prefixArr[end])
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		lx = [arr[0]]
		for i in range(1, len(arr)):
			lx.append(lx[i - 1] ^ arr[i])
		return [lx[i[1]] if i[0] == 0 else lx[i[0] - 1] ^ lx[i[1]] for i in queries]


class Solution:

	def xorQueries(self, A: List[int], queries: List[List[int]]) -> List[int]:
		for i in range(len(A) - 1):
			A[i + 1] ^= A[i]
		return [A[j] ^ A[i - 1] if i else A[j] for (i, j) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		for i in range(1, len(arr)):
			arr[i] ^= arr[i - 1]
		result = []
		for (x, y) in queries:
			if x == 0:
				result.append(arr[y])
			else:
				result.append(arr[y] ^ arr[x - 1])
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix_sum = [arr[0]]
		for i in range(1, len(arr)):
			prefix_sum.append(prefix_sum[-1] ^ arr[i])
		result = []
		for (l, r) in queries:
			result.append(prefix_sum[r])
			if l > 0:
				result[-1] ^= prefix_sum[l - 1]
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		ans = []
		for i in range(1, len(arr)):
			arr[i] ^= arr[i - 1]
		return [arr[j] ^ arr[i - 1] if i > 0 else arr[j] for (i, j) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		if len(arr) == 1:
			return [arr[0] for i in queries]
		table = [arr[0]] * len(arr)
		for i in range(1, len(arr)):
			table[i] = table[i - 1] ^ arr[i]
		out = [0] * len(queries)
		for (i, (l, r)) in enumerate(queries):
			if l > 0:
				out[i] = table[l - 1] ^ table[r]
			else:
				out[i] = table[r]
		return out


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xorarr = [0]
		for n in arr:
			xorarr.append(xorarr[-1] ^ n)
		res = []
		for (i, j) in queries:
			res.append(xorarr[j + 1] ^ xorarr[i])
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xors = [arr[0]]
		n = len(arr)
		for i in range(1, n):
			xors.append(xors[-1] ^ arr[i])
		res = []
		for query in queries:
			(l, r) = query
			temp = xors[r]
			if l != 0:
				temp ^= xors[l - 1]
			res.append(temp)
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xors = []
		xoraccum = 0
		for n in arr:
			xoraccum ^= n
			xors.append(xoraccum)
		ret = []
		for query in queries:
			(l, r) = (query[0], query[1])
			rxor = xors[r]
			lxor = 0 if l == 0 else xors[l - 1]
			ret.append(rxor ^ lxor)
		return ret


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		x = 0
		xors = []
		for i in arr:
			x ^= i
			xors.append(x)
		return [xors[i[1]] ^ xors[i[0]] ^ arr[i[0]] for i in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		if len(arr) == 0:
			return []
		xor_arr = [0 for i in range(len(arr))]
		for (index, v) in enumerate(arr):
			if index == 0:
				xor_arr[index] = arr[index]
			else:
				xor_arr[index] = xor_arr[index - 1] ^ arr[index]
		results = [0 for i in range(len(queries))]
		for (index, query) in enumerate(queries):
			start = query[0]
			end = query[1]
			if start == 0:
				results[index] = xor_arr[end]
			else:
				results[index] = xor_arr[end] ^ xor_arr[start - 1]
		return results


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = [0] * len(arr)
		prefix[0] = arr[0]
		for i in range(1, len(arr)):
			prefix[i] = prefix[i - 1] ^ arr[i]
		ans = []
		for query in queries:
			start = query[0]
			end = query[1]
			if start == 0:
				ans.append(prefix[end])
			else:
				ans.append(prefix[start - 1] ^ prefix[end])
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		prefix = [0 for _ in range(n + 1)]
		for i in range(n):
			prefix[i + 1] = prefix[i] ^ arr[i]
		res = []
		print(prefix)
		for (l, r) in queries:
			print((l, r))
			res.append(prefix[r + 1] ^ prefix[l])
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		cumArr = []
		resultArr = []
		for index in range(len(arr)):
			if index == 0:
				cumArr.insert(index, arr[index])
			else:
				cumArr.insert(index, arr[index] ^ cumArr[index - 1])
		for query in queries:
			left = query[0]
			right = query[1]
			if left is not 0:
				resultArr.append(cumArr[right] ^ cumArr[left - 1])
			else:
				resultArr.append(cumArr[right])
		return resultArr


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		ans = []
		prefix = [0] * n
		prefix[0] = arr[0]
		for i in range(1, n):
			prefix[i] = prefix[i - 1] ^ arr[i]
		for q in queries:
			(l, r) = q
			if l == 0:
				ans.append(prefix[r])
			else:
				ans.append(prefix[r] ^ prefix[l - 1])
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		precompute = []
		xor = 0
		for num in arr:
			xor ^= num
			precompute.append(xor)
		ans = []
		for (s, e) in queries:
			if s == 0:
				ans += [precompute[e]]
			else:
				ans += [precompute[e] ^ precompute[s - 1]]
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = [arr[0]]
		for i in range(1, len(arr)):
			prefix.append(prefix[-1] ^ arr[i])
		result = []
		for (s, e) in queries:
			if s == 0:
				result.append(prefix[e])
			else:
				result.append(prefix[e] ^ prefix[s - 1])
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xored = [None] * len(arr)
		ans = [None] * len(queries)
		xored[0] = arr[0]
		for i in range(1, len(arr)):
			xored[i] = xored[i - 1] ^ arr[i]
		for i in range(len(queries)):
			L = queries[i][0]
			R = queries[i][1]
			if L > 0:
				ans[i] = xored[L - 1] ^ xored[R]
			else:
				ans[i] = xored[R]
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		arr.insert(0, 0)
		for i in range(1, len(arr)):
			arr[i] ^= arr[i - 1]
		return [arr[a] ^ arr[b + 1] for (a, b) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		for i in range(1, len(arr)):
			arr[i] ^= arr[i - 1]
		ret = []
		for (l, r) in queries:
			ret.append(arr[r] if l == 0 else arr[r] ^ arr[l - 1])
		return ret


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		acc = [0]
		for i in range(len(arr)):
			acc.append(acc[i] ^ arr[i])
		result = []
		for q in queries:
			result.append(acc[q[0]] ^ acc[q[1] + 1])
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		pre_xor = [0]
		size_arr = len(arr)
		if size_arr % 2 == 0:
			for i in range(0, size_arr, 2):
				pre_xor.append(pre_xor[i] ^ arr[i])
				pre_xor.append(pre_xor[i + 1] ^ arr[i + 1])
		else:
			pre_xor.append(pre_xor[0] ^ arr[0])
			for i in range(1, size_arr, 2):
				pre_xor.append(pre_xor[i] ^ arr[i])
				pre_xor.append(pre_xor[i + 1] ^ arr[i + 1])
		out_xor = []
		for (L, R) in queries:
			out_xor.append(pre_xor[L] ^ pre_xor[R + 1])
		return out_xor


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		a = arr
		q = queries
		l = []
		for i in range(len(a) - 1):
			a[i + 1] ^= a[i]
		print(a)
		for (i, j) in q:
			if i:
				l.append(a[j] ^ a[i - 1])
			else:
				l.append(a[j])
		return l


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = [None] * len(arr)
		res = [None] * len(queries)
		prefix[0] = arr[0]
		for i in range(1, len(arr)):
			prefix[i] = prefix[i - 1] ^ arr[i]
		for i in range(len(queries)):
			if queries[i][0] == 0:
				res[i] = prefix[queries[i][1]]
				continue
			res[i] = prefix[queries[i][1]] ^ prefix[queries[i][0] - 1]
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		curr = 0
		cum_sum = []
		res = []
		for n in arr:
			curr ^= n
			cum_sum.append(curr)
		for (start, end) in queries:
			x = cum_sum[end] ^ (cum_sum[start - 1] if start > 0 else 0)
			res.append(x)
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xrr = [0 for i in range(len(arr))]
		xrr[0] = arr[0]
		for i in range(1, len(arr)):
			xrr[i] = xrr[i - 1] ^ arr[i]
		res = []
		for q in queries:
			l = q[0]
			r = q[1]
			if l == r:
				res.append(arr[l])
			elif l == 0:
				res.append(xrr[r])
			else:
				res.append(xrr[r] ^ xrr[l - 1])
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:

		def constSeg(tree, n, arr):
			tree[n:] = arr
			for i in range(n - 1, 0, -1):
				tree[i] = tree[2 * i] ^ tree[2 * i + 1]

		def getQuery(beg, end):
			beg += n
			end += n
			ans = 0
			while beg < end:
				if beg & 1:
					ans ^= tree[beg]
					beg += 1
				if end & 1:
					end -= 1
					ans ^= tree[end]
				beg //= 2
				end //= 2
			return ans
		n = len(arr)
		tree = [0] * (2 * len(arr))
		constSeg(tree, len(arr), arr)
		ans = []
		for i in queries:
			ans.append(getQuery(i[0], i[1] + 1))
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = []
		cur = 0
		for num in arr:
			cur = cur ^ num
			prefix.append(cur)
		ans = []
		for (l, r) in queries:
			if l == 0:
				ans.append(prefix[r])
			else:
				ans.append(prefix[l - 1] ^ prefix[r])
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = []
		prev = 0
		for a in arr:
			prefix.append(prev ^ a)
			prev = prev ^ a
		ans = []
		for (left, right) in queries:
			if left == 0:
				ans.append(prefix[right])
			else:
				ans.append(prefix[right] ^ prefix[left - 1])
		return ans


class Solution:
	tree = []
	n = 0

	def SegmentTree(self, arr):
		nonlocal tree, n
		n = len(arr)
		tree = [0] * 2 * n
		for i in range(n):
			tree[i + n] = arr[i]
		for j in range(n - 1, 0, -1):
			tree[j] = tree[2 * j] ^ tree[2 * j + 1]

	def xor(self, frm, to):
		nonlocal tree, n
		frm += n
		to += n
		value = 0
		while frm < to:
			if frm & 1 == 1:
				value ^= tree[frm]
				frm += 1
			if to & 1 == 1:
				to -= 1
				value ^= tree[to]
			frm >>= 1
			to >>= 1
		return value

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		self.SegmentTree(arr)
		result = []
		for query in queries:
			result.append(self.xor(query[0], query[1] + 1))
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xors = []
		x = 0
		for num in arr:
			x ^= num
			xors.append(x)
		ans = []
		for (i, j) in queries:
			if i == 0:
				ans.append(xors[j])
			else:
				ans.append(xors[j] ^ xors[i - 1])
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		out = []
		tree = [0] * (2 * n)
		for i in range(n):
			tree[i + n] = arr[i]
		for i in range(n - 1, 0, -1):
			tree[i] = tree[i << 1] ^ tree[i << 1 | 1]
		for q in queries:
			res = 0
			l = q[0] + n
			r = q[1] + n + 1
			while l < r:
				if l & 1:
					res = res ^ tree[l]
					l = l + 1
				if r & 1:
					r = r - 1
					res = res ^ tree[r]
				l >>= 1
				r >>= 1
			out.append(res)
		return out


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefix = [0]
		for a in arr:
			prefix.append(prefix[-1] ^ a)
		ans = []
		for (l, r) in queries:
			ans.append(prefix[r + 1] ^ prefix[l])
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		if arr == []:
			return []
		res = []
		pre = [arr[0]]
		for i in range(1, len(arr)):
			pre.append(arr[i] ^ pre[-1])
		for i in range(0, len(queries)):
			xor = 0
			if queries[i][0] == queries[i][1]:
				res.append(arr[queries[i][0]])
			elif abs(queries[i][0] - queries[i][1]) == 1:
				res.append(arr[queries[i][0]] ^ arr[queries[i][1]])
			elif queries[i][0] == 0:
				res.append(pre[queries[i][1]])
			else:
				res.append(pre[queries[i][1]] ^ pre[queries[i][0] - 1])
		print(res)
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		for i in range(1, len(arr)):
			arr[i] ^= arr[i - 1]
		for (i, q) in enumerate(queries):
			if q[0] == 0:
				queries[i] = arr[q[1]]
			else:
				queries[i] = arr[q[0] - 1] ^ arr[q[1]]
		return queries


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		acc = list(accumulate([0] + arr, xor))
		return [acc[a] ^ acc[b + 1] for (a, b) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		px = arr[:]
		for i in range(1, len(px)):
			px[i] ^= px[i - 1]
		res = []
		for q in queries:
			(s, e) = (q[0], q[1])
			r = px[e]
			if s:
				r ^= px[s - 1]
			res.append(r)
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		b = [arr[0]]
		for a in arr[1:]:
			b.append(b[-1] ^ a)
		ans = []
		for q in queries:
			r = b[q[1]]
			if q[0] > 0:
				r ^= b[q[0] - 1]
			ans.append(r)
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		store = {}
		n = len(arr)
		curr = 0
		store[-1] = 0
		for i in range(n):
			curr ^= arr[i]
			store[i] = curr
		return [store[b] ^ store[a - 1] for (a, b) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		prefixSum = [0] * len(arr)
		prefixSum[0] = arr[0]
		result = []
		for i in range(1, len(arr)):
			prefixSum[i] = prefixSum[i - 1] ^ arr[i]
		for i in queries:
			if i[0] == 0:
				result.append(prefixSum[i[1]])
				continue
			result.append(prefixSum[i[1]] ^ prefixSum[i[0] - 1])
		return result


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		prefix = [0] * (n + 1)
		for i in range(n):
			prefix[i + 1] = prefix[i] ^ arr[i]
		res = []
		for (x, y) in queries:
			res.append(prefix[y + 1] ^ prefix[x])
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		n = len(arr)
		m = len(queries)
		d = {}
		res = []
		d['0 0'] = arr[0]
		for i in range(1, n):
			key = '{} {}'.format(0, i)
			pkey = '{} {}'.format(0, i - 1)
			d[key] = d[pkey] ^ arr[i]
		print(d)
		for i in range(0, m):
			(u, v) = queries[i]
			s = 0
			key2 = '{u} {v}'.format(u=u, v=v)
			if key2 in d:
				res.append(d[key2])
				continue
			pkey = '{} {}'.format(0, u - 1)
			key = '{} {}'.format(0, v)
			s = d[pkey] ^ d[key]
			print(d[pkey], d[key], s)
			res.append(s)
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		res = []
		n = len(arr)
		tmp = [arr[0]]
		for i in range(1, n):
			tmp.append(tmp[-1] ^ arr[i])
		for (x, y) in queries:
			if x == 0:
				res.append(tmp[y])
			else:
				res.append(tmp[x - 1] ^ tmp[y])
		return res


from itertools import accumulate
import operator

class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		x = list(accumulate(arr, operator.__xor__, initial=0))
		return [x[i] ^ x[j + 1] for (i, j) in queries]


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		ans = []
		a = [arr[0]]
		for i in range(1, len(arr)):
			a.append(arr[i] ^ a[i - 1])
		for q in queries:
			if q[0] == 0:
				ans.append(a[q[1]])
			else:
				ans.append(a[q[1]] ^ a[q[0] - 1])
		return ans


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xor_arr = [0] * len(arr)
		xor_arr[0] = arr[0]
		for i in range(1, len(arr)):
			xor_arr[i] = xor_arr[i - 1] ^ arr[i]
		res = [0] * len(queries)
		for (i, (s, e)) in enumerate(queries):
			if s == e:
				res[i] = arr[s]
			elif s == 0:
				res[i] = xor_arr[e]
			else:
				res[i] = xor_arr[e] ^ xor_arr[s - 1]
		return res


class Solution:

	def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
		xors = [0]
		for a in arr:
			xors.append(xors[-1] ^ a)
		res = []
		for (i, j) in queries:
			res.append(xors[j + 1] ^ xors[i])
		return res