Nitika recently read about XOR operation and she got obssessed with it. She has an array a containing N Positive integers.She wants to perform Q queries on the array.In a query She gives two integers L and R.(1 based indexing).Now, she asks what is the xor of all the elements of the array after not including the subarray ranging from L to R (both inclusive).Nitika guarantees that in each query, The resulting array is non empty. The queries are given in a 2D matrix query having L and R for each entry. 
Example 1:
Input: N = 10, Q = 3
a = {4, 7, 8, 5, 9, 6, 1, 0, 20, 10}
query = {{3, 8},{1, 6},{2, 3}}
Output: 
29
31
17
Explaination: For the first query: 
The resulting array is: (4 ,7 ,20, 10).
Their Xor will be: 29. 
For the Second query: The resulting 
array is: (1, 0, 20, 10). Their Xor 
will be: 31. 
For the Third query:  The resulting 
array is: (4, 5, 9, 6, 1,0 ,20, 10). 
Their Xor will be: 17.
Your Task:
you do not need to read input or print anything. Your task is to complete the function specialXor() which takes N, Q, a[] and query as input parameters and returns a list containing answer for each query.
Expected Time Complexity: O(N+Q*logN)
Expected Auxiliary Space: O(N+Q)
Constraints:
1 ≤ N, Q ≤ 10^{5}
1 ≤ A[i] ≤ 10^{9}
1 ≤ L, R ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3



class Solution:

    def specialXor(self, N, Q, a, query):

        # code here

Solutions:
class SegmentTree:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr)
		self.seg = [0] * self.n * 4

		def build(ind, low, high):
			if low == high:
				self.seg[ind] = arr[low]
				return
			mid = low + high >> 1
			build(ind * 2 + 1, low, mid)
			build(ind * 2 + 2, mid + 1, high)
			self.seg[ind] = self.seg[ind * 2 + 1] ^ self.seg[ind * 2 + 2]
		build(0, 0, self.n - 1)

	def query(self, ind, low, high, l, r):
		if low > r or l > high:
			return 0
		if low >= l and high <= r:
			return self.seg[ind]
		mid = low + high >> 1
		left = self.query(ind * 2 + 1, low, mid, l, r)
		right = self.query(ind * 2 + 2, mid + 1, high, l, r)
		return left ^ right

class Solution:

	def specialXor(self, N, Q, a, query):
		s = SegmentTree(a)
		ans = 0
		for i in a:
			ans ^= i
		res = []
		for (i, j) in query:
			temp = s.query(0, 0, N - 1, i - 1, j - 1)
			res.append(ans ^ temp)
		return res


class Solution:

	def specialXor(self, N, Q, a, query):
		for i in range(1, len(a)):
			a[i] ^= a[i - 1]
		return [a[-1] ^ (a[r - 1] ^ (a[l - 2] if l - 2 >= 0 else 0)) for (l, r) in query]


class Solution:

	def specialXor(self, N, Q, a, query):
		prefix = [0]
		for i in range(N):
			prefix.append(prefix[-1] ^ a[i])
		res = []
		for q in query:
			(l, r) = q
			res.append(prefix[r] ^ prefix[l - 1] ^ prefix[-1])
		return res


class Solution:

	def specialXor(self, N, Q, a, query):
		tree = [0] * (2 * N)

		def get(l, r):
			l += N - 1
			r += N - 1
			res = 0
			while l <= r:
				if l % 2 == 1:
					res ^= tree[l]
					l += 1
				if r % 2 == 0:
					res ^= tree[r]
					r -= 1
				l //= 2
				r //= 2
			return res

		def update(pos, val):
			pos += N - 1
			tree[pos] = val
			pos //= 2
			while pos >= 1:
				tree[pos] = tree[2 * pos] ^ tree[2 * pos + 1]
				pos //= 2
		for (i, x) in enumerate(a):
			update(i + 1, x)
		res = []
		for (a, b) in query:
			res.append(get(1, a - 1) ^ get(b + 1, N))
		return res


class Solution:

	def specialXor(self, N, Q, a, Query):
		n_xor = 0
		for i in a:
			n_xor ^= i
		seg = [0] * (4 * N)

		def query(idx, low, high, l, r):
			if low >= l and high <= r:
				return seg[idx]
			if high < l or low > r:
				return 0
			mid = (low + high) // 2
			left = query(2 * idx + 1, low, mid, l, r)
			right = query(2 * idx + 2, mid + 1, high, l, r)
			return left ^ right

		def build(idx, low, high):
			if low == high:
				seg[idx] = a[low]
				return
			mid = (low + high) // 2
			build(2 * idx + 1, low, mid)
			build(2 * idx + 2, mid + 1, high)
			seg[idx] = seg[2 * idx + 1] ^ seg[2 * idx + 2]
		build(0, 0, N - 1)
		ans = []
		for (i, j) in Query:
			x = query(0, 0, N - 1, i - 1, j - 1)
			ans.append(n_xor ^ x)
		return ans


class Segment:

	def __init__(self, arr):
		self.arr = arr
		self.tree = [None for i in range(4 * len(self.arr))]

	def constructHelper(self, ss, se, si):
		if ss == se:
			self.tree[si] = self.arr[ss]
			return self.tree[si]
		mid = (ss + se) // 2
		self.tree[si] = self.constructHelper(ss, mid, 2 * si + 1) ^ self.constructHelper(mid + 1, se, 2 * si + 2)
		return self.tree[si]

	def constructTree(self):
		self.constructHelper(0, len(self.arr) - 1, 0)

	def getXorHelper(self, qs, qe, ss, se, si):
		if qe < ss or qs > se:
			return 0
		if qs <= ss and qe >= se:
			return self.tree[si]
		mid = (ss + se) // 2
		return self.getXorHelper(qs, qe, ss, mid, 2 * si + 1) ^ self.getXorHelper(qs, qe, mid + 1, se, 2 * si + 2)

	def getXor(self, qs, qe):
		return self.getXorHelper(qs, qe, 0, len(self.arr) - 1, 0)

class Solution:

	def specialXor(self, N, Q, a, query):
		seg = Segment(a)
		seg.constructTree()
		now = 0
		curr = seg.getXor(0, N - 1)
		res = []
		for i in range(Q):
			(p, q) = (query[i][0] - 1, query[i][1] - 1)
			res.append(curr ^ seg.getXor(p, q))
		return res


class Solution:

	def specialXor(self, n, Q, nums, query):
		prefixXor = [0]
		for i in range(n):
			prefixXor.append(prefixXor[-1] ^ nums[i])
		ans = []
		for (l, r) in query:
			ans.append(prefixXor[r] ^ prefixXor[l - 1] ^ prefixXor[-1])
		return ans


from math import ceil, log2

class Solution:

	def buildST(self, st, a, ss, se, ci):
		if ss == se:
			st[ci] = a[ss]
			return st[ci]
		mid = (ss + se) // 2
		st[ci] = self.buildST(st, a, ss, mid, 2 * ci + 1) ^ self.buildST(st, a, mid + 1, se, 2 * ci + 2)
		return st[ci]

	def getRangeXOR(self, st, qs, qe, ss, se, ci):
		if se < qs or ss > qe:
			return None
		if qs <= ss and se <= qe:
			return st[ci]
		mid = (ss + se) // 2
		l = self.getRangeXOR(st, qs, qe, ss, mid, 2 * ci + 1)
		r = self.getRangeXOR(st, qs, qe, mid + 1, se, 2 * ci + 2)
		if l != None and r != None:
			return l ^ r
		if l == None and r != None:
			return r
		if r == None and l != None:
			return l
		return None

	def specialXor(self, N, Q, a, query):
		h = int(ceil(log2(N)))
		st = [0] * (2 ** (h + 1) - 1)
		self.buildST(st, a, 0, N - 1, 0)
		results = []
		for rangee in query:
			(qs, qe) = (min(rangee) - 1, max(rangee) - 1)
			rxor = self.getRangeXOR(st, qs, qe, 0, N - 1, 0)
			results.append(st[0] ^ rxor)
		return results


import math

class Solution:

	def specialXor(self, N, Q, a, query):
		max_size = 2 * 2 ** math.ceil(math.log(N, 2)) - 1
		tree = [0] * max_size

		def construct(si, s, e):
			if s == e:
				tree[si] = a[s]
				return tree[si]
			mid = (s + e) // 2
			tree[si] = construct(2 * si + 1, s, mid) ^ construct(2 * si + 2, mid + 1, e)
			return tree[si]

		def getxor(ss, se, qs, qe, si):
			if ss > qe or se < qs:
				return 0
			if ss >= qs and qe >= se:
				return tree[si]
			mid = (ss + se) // 2
			return getxor(ss, mid, qs, qe, 2 * si + 1) ^ getxor(mid + 1, se, qs, qe, 2 * si + 2)
		construct(0, 0, N - 1)
		xr = 0
		for i in a:
			xr ^= i
		ans = [0] * Q
		for i in range(Q):
			ans[i] = xr ^ getxor(0, N - 1, query[i][0] - 1, query[i][1] - 1, 0)
		return ans


class STree:

	def __init__(self, n):
		self.BIT = [0] * (2 * N)
		self.N = n

	def build(self, A):
		for i in range(self.N):
			idx = i + self.N
			self.BIT[idx] = A[i]
		for i in range(self.N - 1, 0, -1):
			self.BIT[i] = self.BIT[2 * i] ^ self.BIT[2 * i + 1]

	def update(self, idx, val):
		idx += self.N
		self.BIT[idx] = val
		while idx > 1:
			self.BIT[idx >> 1] = self.BIT[idx] ^ self.BIT[idx ^ 1]
			idx >>= 1

	def query(self, l, r):
		l += self.N
		r += self.N
		ans = 0
		while l <= r:
			if l & 1:
				ans ^= self.BIT[l]
				l += 1
			if r & 1 == 0:
				ans ^= self.BIT[r]
				r -= 1
			l >>= 1
			r >>= 1
		return ans

class Solution:

	def specialXor(self, N, Q, A, query):
		tree = STree(N)
		tree.build(A)
		ans = []
		for q in query:
			(l, r) = (q[0] - 1, q[1] - 1)
			if l == 0 and r == N - 1:
				ans.append(0)
			elif l == 0:
				ans.append(tree.query(r + 1, N - 1))
			elif r == N - 1:
				ans.append(tree.query(0, l - 1))
			else:
				ans.append(tree.query(0, l - 1) ^ tree.query(r + 1, N - 1))
		return ans


class Solution:

	def specialXor(self, N, Q, a, query):
		for i in range(1, len(a)):
			a[i] ^= a[i - 1]
		main = a[len(a) - 1]
		ans = []
		val = 0
		val1 = 0
		for i in range(Q):
			if query[i][0] == 1:
				val = a[query[i][1] - 1]
				ans.append(main ^ val)
			else:
				val = a[query[i][1] - 1] ^ a[query[i][0] - 2]
				ans.append(main ^ val)
		return ans


class Solution:

	def specialXor(self, N, Q, a, query):
		pre = [a[0]]
		pos = [a[-1]]
		for i in a[1:]:
			pre.append(pre[-1] ^ i)
		for i in a[-2::-1]:
			pos.append(pos[-1] ^ i)
		ret = []
		for (i, j) in query:
			if i - 2 < 0:
				ret.append(pos[N - j - 1])
			elif N - j - 1 < 0:
				ret.append(pre[i - 2])
			else:
				ret.append(pre[i - 2] ^ pos[N - j - 1])
		return ret


class Solution:

	def specialXor(self, n, q, a, query):
		l = [0]
		t = 0
		for val in a:
			t ^= val
			l.append(t)
		ans = []
		for val in query:
			ans.append(l[val[1]] ^ l[val[0] - 1] ^ l[n])
		return ans


class Solution:

	def specialXor(self, N, Q, a, query):
		arr = [a[0]]
		for i in range(1, N):
			arr.append(arr[-1] ^ a[i])
		ans = []
		for q in query:
			(l, r) = q
			(l, r) = (l - 1, r - 1)
			if l == 0:
				ans.append(arr[N - 1] ^ arr[r])
			else:
				ans.append(arr[N - 1] ^ arr[l - 1] ^ arr[r])
		return ans


class Solution:

	def specialXor(self, N, Q, a, query):
		x = [0] * (N + 1)
		for i in range(1, N + 1):
			x[i] = x[i - 1] ^ a[i - 1]
		final = []
		for i in query:
			(l, r) = (i[0], i[1])
			s = x[l - 1]
			t = x[-1] ^ x[r]
			final.append(s ^ t)
		return final


class Solution:

	def specialXor(self, n, q, arr, query):
		lis1 = [arr[0]]
		xor1 = arr[0]
		xor2 = arr[-1]
		lis2 = [arr[-1]]
		for i in range(1, n):
			xor1 = xor1 ^ arr[i]
			lis1.append(xor1)
			xor2 = xor2 ^ arr[-1 * (i + 1)]
			lis2.append(xor2)
		xors = []
		for i in range(0, len(query)):
			if query[i][0] != 1 and query[i][1] != len(arr):
				xor = lis1[query[i][0] - 2] ^ lis2[-1 * (query[i][1] + 1)]
				xors.append(xor)
			if query[i][0] == 1:
				xors.append(lis2[-1 * (query[i][1] + 1)])
			if query[i][1] == len(arr):
				xors.append(lis1[query[i][0] - 1])
		return xors


class Solution:

	def build(self, index, low, high, arr, seg_arr):
		if low == high:
			seg_arr[index] = arr[low]
			return
		mid = low + (high - low) // 2
		left_index = 2 * index + 1
		right_index = 2 * index + 2
		self.build(left_index, low, mid, arr, seg_arr)
		self.build(right_index, mid + 1, high, arr, seg_arr)
		seg_arr[index] = seg_arr[left_index] ^ seg_arr[right_index]
		return

	def query_res(self, index, low, high, arr, seg_arr, L, R):
		if high < L or R < low:
			return 0
		if L <= low and high <= R:
			return seg_arr[index]
		mid = low + (high - low) // 2
		left_index = 2 * index + 1
		right_index = 2 * index + 2
		left_val = self.query_res(left_index, low, mid, arr, seg_arr, L, R)
		right_val = self.query_res(right_index, mid + 1, high, arr, seg_arr, L, R)
		return left_val ^ right_val

	def specialXor(self, N, Q, a, query):
		xor = 0
		for x in a:
			xor = xor ^ x
		seg_arr = [0] * (4 * N)
		self.build(0, 0, N - 1, a, seg_arr)
		tmp_list = []
		for i in range(Q):
			(L, R) = (query[i][0] - 1, query[i][1] - 1)
			val = self.query_res(0, 0, N - 1, a, seg_arr, L, R)
			tmp_list.append(val ^ xor)
		return tmp_list


from functools import reduce

class Solution:

	def specialXor(self, N, Q, a, query):
		ps = [0] * N
		ps[0] = a[0]
		for i in range(1, N):
			ps[i] = a[i] ^ ps[i - 1]
		ps1 = [0] * N
		ps1[N - 1] = a[N - 1]
		for i in range(N - 2, -1, -1):
			ps1[i] = a[i] ^ ps1[i + 1]
		res = []
		for i in range(Q):
			l = query[i][0]
			r = query[i][1]
			if l == 1:
				val = ps1[r]
			else:
				val = ps[l - 2] ^ ps1[r]
			res.append(val)
		return res


class segmentTree:

	def __init__(self, arr):
		self.size = 1
		while self.size < len(arr):
			self.size *= 2
		self.values = [0] * (2 * self.size - 1)
		self.build(arr, 0, self.size, 0)

	def build(self, arr, left, right, i):
		if right - left == 1:
			if left < len(arr):
				self.values[i] = arr[left]
			return
		mid = (left + right) // 2
		self.build(arr, left, mid, 2 * i + 1)
		self.build(arr, mid, right, 2 * i + 2)
		self.values[i] = self.values[2 * i + 1] ^ self.values[2 * i + 2]

	def getQuery(self, a, b, left, right, i):
		if a >= right or b <= left:
			return 0
		if a <= left and b >= right:
			return self.values[i]
		mid = (left + right) // 2
		return self.getQuery(a, b, left, mid, 2 * i + 1) ^ self.getQuery(a, b, mid, right, 2 * i + 2)

class Solution:

	def specialXor(self, N, Q, a, query):
		st = segmentTree(a)
		ans = []
		for q in query:
			first = st.getQuery(0, q[0] - 1, 0, st.size, 0)
			second = st.getQuery(q[1], st.size, 0, st.size, 0)
			ans.append(second ^ first)
		return ans


def build(tree, arr, start, end, treeIndex):
	if start == end:
		tree[treeIndex] = arr[start]
		return
	mid = (start + end) // 2
	build(tree, arr, start, mid, treeIndex * 2 + 1)
	build(tree, arr, mid + 1, end, treeIndex * 2 + 2)
	tree[treeIndex] = tree[treeIndex * 2 + 1] ^ tree[treeIndex * 2 + 2]

def Query(tree, start, end, left, right, treeIndex):
	if start > right or end < left:
		return 0
	elif start >= left and end <= right:
		return tree[treeIndex]
	mid = (start + end) // 2
	ans1 = Query(tree, start, mid, left, right, treeIndex * 2 + 1)
	ans2 = Query(tree, mid + 1, end, left, right, treeIndex * 2 + 2)
	return ans1 ^ ans2

class Solution:

	def specialXor(self, N, Q, a, query):
		tree = [0] * (4 * N + 1)
		build(tree, a, 0, N - 1, 0)
		ans = []
		for i in query:
			l = i[0]
			r = i[1]
			ans1 = Query(tree, 0, N - 1, l - 1, r - 1, 0)
			ans.append(tree[0] ^ ans1)
		return ans


class segmentTree:

	def __init__(self, N):
		self.n = N
		self.tree = [0] * 2 * N

	def build(self, arr):
		for i in range(self.n):
			self.tree[self.n + i] = arr[i]
		for i in range(self.n - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] ^ self.tree[i << 1 | 1]

	def updateTreeNode(self, p, value):
		self.tree[p + self.n] = value
		p = p + self.n
		i = p
		while i > 1:
			self.tree[i >> 1] = self.tree[i] ^ self.tree[i ^ 1]
			i >>= 1

	def query(self, l, r):
		res = 0
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				res ^= self.tree[l]
				l += 1
			if r & 1:
				r -= 1
				res ^= self.tree[r]
			l >>= 1
			r >>= 1
		return res

class Solution:

	def specialXor(self, N, Q, a, query):
		tree = segmentTree(N)
		tree.build(a)
		results = []
		for interval in query:
			results.append(tree.query(0, interval[0] - 1) ^ tree.query(interval[1], N))
		return results


class Solution:

	def specialXor(self, N, Q, a, query):
		results = []
		base = 0
		forward = []
		backward = []
		for x in a:
			base ^= x
			forward.append(base)
		reverse = 0
		for x in a[::-1]:
			reverse ^= x
			backward.insert(0, reverse)
		for (begin, end) in query:
			xor = 0
			if begin - 1:
				xor ^= forward[begin - 2]
			if end < N:
				xor ^= backward[end]
			results.append(xor)
		return results


def xor(t, s, e, l, r, i):
	if l <= s and r >= e:
		return t[i]
	if l > e or r < s:
		return 0
	m = (s + e) // 2
	return xor(t, m + 1, e, l, r, 2 * i + 2) ^ xor(t, s, m, l, r, 2 * i + 1)

def buildTree(t, a, s, e, i):
	if s == e:
		t[i] = a[s]
		return t[i]
	mid = (s + e) // 2
	l = buildTree(t, a, s, mid, i * 2 + 1)
	r = buildTree(t, a, mid + 1, e, i * 2 + 2)
	t[i] = l ^ r
	return t[i]

class Solution:

	def specialXor(self, N, Q, a, query):
		ans = a[0]
		for i in range(1, N):
			ans ^= a[i]
		res = []
		tree = [0] * (4 * N)
		buildTree(tree, a, 0, N - 1, 0)
		for q in query:
			l = q[0] - 1
			r = q[1] - 1
			x = xor(tree, 0, N - 1, l, r, 0)
			x = x ^ ans
			res.append(x)
		return res


def solve(tree, start, end, ss, se, si):
	if se < start or ss > end:
		return 0
	if ss <= start and se >= end:
		return tree[si]
	mid = (start + end) // 2
	if ss > mid:
		return solve(tree, mid + 1, end, ss, se, si * 2 + 2)
	if se <= mid:
		return solve(tree, start, mid, ss, se, si * 2 + 1)
	left = solve(tree, start, mid, ss, se, si * 2 + 1)
	right = solve(tree, mid + 1, end, ss, se, si * 2 + 2)
	return left ^ right

def build(tree, start, end, a, si):
	if start == end:
		tree[si] = a[start]
		return
	mid = (start + end) // 2
	build(tree, start, mid, a, si * 2 + 1)
	build(tree, mid + 1, end, a, si * 2 + 2)
	tree[si] = tree[si * 2 + 1] ^ tree[si * 2 + 2]

class Solution:

	def specialXor(self, N, Q, a, query):
		tree = [0] * (4 * N)
		build(tree, 0, N - 1, a, 0)
		total = 0
		ans = []
		for i in range(N):
			total ^= a[i]
		for i in range(Q):
			xor = solve(tree, 0, N - 1, query[i][0] - 1, query[i][1] - 1, 0)
			ans.append(xor ^ total)
		return ans


def build(a, l, r, tree, si):
	if l == r:
		tree[si] = a[l]
		return a[l]
	mid = (l + r) // 2
	left = build(a, l, mid, tree, si * 2 + 1)
	right = build(a, mid + 1, r, tree, si * 2 + 2)
	tree[si] = left ^ right
	return tree[si]

def queries(tree, s, e, l, r, si):
	if l <= s and r >= e:
		return tree[si]
	if l > e or r < s:
		return 0
	mid = (s + e) // 2
	return queries(tree, s, mid, l, r, si * 2 + 1) ^ queries(tree, mid + 1, e, l, r, si * 2 + 2)

class Solution:

	def specialXor(self, N, Q, a, query):
		tree = [0] * (4 * N)
		ans = []
		build(a, 0, N - 1, tree, 0)
		res = 0
		for i in range(N):
			res = res ^ a[i]
		for i in range(Q):
			x = queries(tree, 0, N - 1, query[i][0] - 1, query[i][1] - 1, 0)
			x = x ^ res
			ans.append(x)
		return ans


from math import ceil, log2

class Solution:

	def getmid(self, start, end):
		return start + (end - start) // 2

	def constructTree(self, arr, start, end, tree, treei):
		if start == end:
			tree[treei] = arr[start]
		else:
			mid = self.getmid(start, end)
			l = self.constructTree(arr, start, mid, tree, treei * 2 + 1)
			r = self.constructTree(arr, mid + 1, end, tree, treei * 2 + 2)
			tree[treei] = l ^ r
		return tree[treei]

	def buildtree(self, arr, n):
		height = int(ceil(log2(n)))
		maxsize = 2 * pow(2, height) - 1
		tree = [-1] * maxsize
		self.constructTree(arr, 0, n - 1, tree, 0)
		return tree

	def getsum(self, tree, treei, ss, se, qs, qe):
		if qs <= ss and qe >= se:
			return tree[treei]
		if qe < ss or qs > se:
			return -1
		mid = self.getmid(ss, se)
		l = self.getsum(tree, 2 * treei + 1, ss, mid, qs, qe)
		r = self.getsum(tree, 2 * treei + 2, mid + 1, se, qs, qe)
		if l != -1 and r != -1:
			return l ^ r
		if l == -1:
			return r
		return l

	def getsumrange(self, tree, n, l, r):
		return self.getsum(tree, 0, 0, n - 1, l, r)

	def specialXor(self, N, Q, arr, queries):
		tree = self.buildtree(arr, N)
		whole = arr[0]
		for x in arr[1:]:
			whole = whole ^ x
		res = []
		for query in queries:
			res.append(whole ^ self.getsumrange(tree, N, query[0] - 1, query[1] - 1))
		return res