1.
Problem
2.
Solution
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Finding XOR of the Array Elements in a Given Range with Updates using Fenwick Tree

GAZAL ARORA
0 upvote

Prerequisites: Binary Indexed Tree.

## Problem

Given an array A of size n and an array Q of size q containing the following two types of queries:

• (1, L, R): Return the XOR of all elements present between the array indices L and R.
• (2, i, value): Update the value of A[i] to (A[i] XOR value).

Solve each Query using Fenwick Tree and print the result of every Query of 1st type.

Input:

• An integer n.
• The next n lines contain the array elements.
• The next line contains an integer q that represents the size of the Q array.
• The next q lines contain queries to resolve.

Output:  Print the result of every Query of 1st type in a new line.

Questions you can ask the interviewer:

1. What are the constraints on n and q?
2. What is the range of the elements of A?

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Example,

Recommended: Try to solve it yourself before moving on to the solution.

## Solution

Idea: The idea is to solve it using Fenwick TreeBuild Binary Index Tree of the array elements.

Define a getXOR(x) function that will return the XOR of array elements with index range [1, x].

For queries of Type1: For XOR of range [ l, r], return the Xor of elements in range [1, R] and range[1, L-1] i.e. ( getXOR(r) XOR getXOR(l-1) ).

For queries of Type2: Define an updateBITree function that will update the values in  Binary Index Tree according to the queries.

Algorithm:

• In getXOR(), keep computing XOR using BinTree[i] for starting index i to all its ancestors until 1. In the getXOR(), subtract LSB(least Significant Bit) from i as i = i – i&(-i) to get the ancestor of the i-th index. Return the XOR computed.
• In updateBITree(), update A[i] to A[i] ^ value. Update all ranges that include this index in BITree using the updateBIT() function.
• In updateBITree(), to get ancestor of i-th index, add LSB(least Significant Bit) to i: i = i + i&(-i).

C++

Input: n = 9, A = {1, 2, 3, 4, 5, 6, 7, 8, 9}, q = 3, Q = {{ 1, 2, 5}, {2, 4, 2}, {1, 2, 5}}.

Output:

Time complexity: O(q * logn)

Time complexity of getXOR(): O(logn).

Time complexity of updateBITree(): O(long).

## FAQs

1. What is a Binary Indexed Tree?
A Binary Indexed Tree (BIT), also known as a Fenwick Tree, is a data structure used for efficiently calculating and updating additive frequency tables or prefix sums.

2. What is the B tree index?
A B-tree index is a multi-level tree structure that divides a database into blocks or pages of a specific size. Each level in this tree can link those sites together using an address location, allowing a page to refer to another at the lowest level using leaf pages.

## Key Takeaways

In this article, we designed an algorithm to find the XOR of array elements in a given range with updates of array values using the Fenwick Tree. The algorithm's time complexity is O(q * logn), where q is the query array's size, and n is the size of array A.

Use Coding Ninjas Studio to practice various DSA questions asked in many interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Live masterclass