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.

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.

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

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:

What are the constraints on n and q?
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,

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:

XOR of the elements between 2 to 5 is 4.

XOR of the elements between 2 to 5 is 6.

Explanation:

The XOR of the subarray { 3, 4, 5, 6 } is 4.
After the 2nd query A[4] becomes A[4]^2 = 5^2 = 7.
The XOR of subarray {3, 4, 7, 6 } is 6.

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

Solution

Idea: The idea is to solve it using Fenwick Tree. Build 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++

#include <bits/stdc++.h>
using namespace std;

// Returns the XOR of A[0..i].
int getXOR(vector<int> &BITree, int i)
{
int res = 0;
i++;

// Traverse across the ancestors of BITree[i].
while (i > 0) {

//update XOR.
res ^= BITree[i];
// Move to the parent node.
i = i- (i & (-i));
}
return res;
}

void updateBITree(vector<int> &BITree, int i, int n, int val)
{
i++;
// Traverse all ancestors update the value.
while (i <= n) {

BITree[i] = BITree[i]^val;
// Move to the parent node.
i = i + (i & (-i));
}
}

// Construct and return the Binary Indexed Tree.
vector<int> buildBITree(int n, int A[])
{
vector<int> BITree(n+1);

// Update values in BIT using updateBIT.
for (int i = 0; i < n; i++)
updateBITree(BITree, i, n, A[i]);

return BITree;
}

int xorRange(vector<int> &BITree, int l, int r)
{
return getXOR(BITree, r) ^ getXOR(BITree, l-1);
}

int main()
{
int n = 9;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9 };

int q = 3;
vector<vector<int> > Q = { { 1, 2, 5}, {2, 4, 2}, {1, 2, 5}};

// Create the Binary Indexed Tree
vector<int> BITree = buildBITree(n, A);

// Solve for every query in Q.
for (int i = 0; i < q; i++) {
int type = Q[i][0];

if (type == 1) {
int L = Q[i][1];
int R = Q[i][2];
cout << "XOR of the elements between "<<L<<" to "<<R<<" is "<<xorRange(BITree, L, R)<< "\n";
}
else {
int index = Q[i][1];
int value = Q[i][2];
A[index] = A[index]^value;

// Update the values in BITree.
updateBITree(BITree, index, n, value);
}
}
return 0;
}

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

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.
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.