You are given an array nums. Your task is to complete the function getXor to return the XOR of the given range a and b.
 
Example 1:
Input: nums = {1, 3, 5, 7, 9, 11}
,a = 1, b = 3
Output: 1
Explanation: 3^5^7 = 1
Example 2:
Input: nums = {1, 2, 3, 4, 5}
a = 0, b = 4
Output: 1
 
Your Task:
You don't need to read or print anyhting. Your task is to comlplete the function getXor() which takes nums, a and b as input parameter and returns the xor from a to b.
 
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
 
Constraints:
1 ≤ n ≤ 10^{5}
0 ≤ a ≤ b < n
1 ≤ nums[i] ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Segment trees revisited

Starter code: class Solution:

    def getXor(self, nums, a, b):

        ans = 0

        for i in range(a, b+1):

            ans = ans ^ nums[i]

        return ans

Solutions:
class Solution:

	def getXor(self, nums, a, b):
		ans = 0
		for i in range(a, b + 1):
			ans = ans ^ nums[i]
		return ans


class SegmentTree:

	def __init__(self, nums):
		self.nums = nums
		self.length = len(nums)
		self.segmentTree = [0] * (self.length * 4)
		self.construct(start=0, end=self.length - 1, currentIndex=0)

	def construct(self, start, end, currentIndex):
		if start == end:
			self.segmentTree[currentIndex] = self.nums[start] ^ 0
			return
		mid = start + (end - start) // 2
		self.construct(start, mid, 2 * currentIndex + 1)
		self.construct(mid + 1, end, 2 * currentIndex + 2)
		self.segmentTree[currentIndex] = self.segmentTree[2 * currentIndex + 1] ^ self.segmentTree[2 * currentIndex + 2]
		return

	def update(self, value, index, start=0, end=None, currentIndex=0):
		if end == None:
			end = self.length - 1
		if currentIndex == 0:
			self.nums[index] = value
		if start == end:
			self.segmentTree[currentIndex] = self.nums[index]
		mid = start + (end - start) // 2
		if index <= mid:
			self.update(value, index, start, mid, 2 * currentIndex + 1)
		else:
			self.update(value, index, mid + 1, end, 2 * currentIndex + 2)
		self.segmentTree[currentIndex] = self.segmentTree[2 * currentIndex + 1] ^ self.segmentTree[2 * currentIndex + 2]
		return

	def rangeMin(self, left, right, start=0, end=None, currentIndex=0):
		if end == None:
			end = self.length - 1
		if left > end or start > right:
			return 0
		if left <= start and right >= end:
			return self.segmentTree[currentIndex]
		mid = start + (end - start) // 2
		leftMin = self.rangeMin(left, right, start, mid, 2 * currentIndex + 1)
		rightMin = self.rangeMin(left, right, mid + 1, end, 2 * currentIndex + 2)
		return leftMin ^ rightMin

class Solution:

	def __init__(self):
		self.S = None

	def getXor(self, nums, a, b):
		self.S = SegmentTree(nums)
		return self.S.rangeMin(a, b)


class Solution:

	def getXor(self, nums, a, b):
		n = len(nums)
		tree = [0] * (n + 1)

		def update_fenwick(i, val):
			while i <= n:
				tree[i] ^= val
				i += i & -i

		def get_fenwick(i):
			ans = 0
			while i:
				ans ^= tree[i]
				i -= i & -i
			return ans
		for i in range(1, len(nums) + 1):
			update_fenwick(i, nums[i - 1])
		return get_fenwick(b + 1) ^ get_fenwick(a)


def build(si, ss, se, arr, st):
	if ss > se:
		return
	elif ss == se:
		st[si] = arr[ss]
	else:
		mid = (ss + se) // 2
		build(2 * si + 1, ss, mid, arr, st)
		build(2 * si + 2, mid + 1, se, arr, st)
		st[si] = st[2 * si + 1] ^ st[2 * si + 2]

def query(si, ss, se, qs, qe, st):
	if ss > qe or se < qs:
		return 0
	elif qs <= ss and se <= qe:
		return st[si]
	else:
		mid = (ss + se) // 2
		return query(2 * si + 1, ss, mid, qs, qe, st) ^ query(2 * si + 2, mid + 1, se, qs, qe, st)

class Solution:

	def getXor(self, nums, a, b):
		st = [0] * (4 * len(nums) + 10)
		build(0, 0, len(nums) - 1, nums, st)
		return query(0, 0, len(nums) - 1, a, b, st)


class Solution:

	def getXor(self, nums, a, b):
		ans = 0
		for i in range(a, b + 1):
			ans = ans ^ nums[i]
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, a, b) = map(int, input().strip().split())
		nums = list(map(int, input().strip().split()))
		if a > b:
			(a, b) = (b, a)
		obj = Solution()
		ans = obj.getXor(nums, a, b)
		print(ans)


class Solution:

	def getXor(self, nums, a, b):
		res = nums[a]
		for i in range(a + 1, b + 1):
			res ^= nums[i]
		return res


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

def query(arr, start, end, left, right, index):
	global tree
	if start > left or end < right:
		return 0
	elif start >= left and end <= right:
		return tree[index]
	else:
		mid = (start + end) // 2
		ans1 = query(arr, start, mid, left, right, index)
		ans2 = query(arr, mid + 1, end, left, right, index)
		return ans1 ^ ans2

class Solution:

	def getXor(self, nums, a, b):
		ans = 0
		for i in range(a, b + 1):
			ans ^= nums[i]
		return ans


class Solution:

	def getXor(self, nums, a, b):
		c = nums[a]
		for x in range(a + 1, b + 1):
			c ^= nums[x]
		return c


def build(tree, a, s, e, si):
	if s == e:
		tree[si] = a[s]
		return a[s]
	mid = (s + e) // 2
	left = build(tree, a, s, mid, si * 2 + 1)
	right = build(tree, a, mid + 1, e, 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 e < l or s > r:
		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 getXor(self, nums, a, b):
		tree = [0] * (4 * len(nums))
		build(tree, nums, 0, len(nums) - 1, 0)
		x = queries(tree, 0, len(nums) - 1, a, b, 0)
		return x


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

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

class Solution:

	def getXor(self, nums, a, b):
		tree = [0] * (4 * len(nums))
		build(tree, nums, 0, len(nums) - 1, 0)
		return solve(tree, 0, len(nums) - 1, a, b, 0)