Binary Indexed Trees (Fenwick Trees)

Binary Indexed Trees, also known as Fenwick Trees, are efficient data structures used for querying and updating cumulative frequency or prefix sum arrays. We can modify the Fenwick Tree to support bitwise XOR operations and use it to compute the XOR of numbers in the given range efficiently.

Example: Consider an example where L=3 and R=7. We construct a Fenwick Tree for the given range and then query it to find the XOR of numbers from 3 to 7.

JavaScript

// Update Binary Indexed Tree (Fenwick Tree)
function updateBIT(BIT, index, val) {
    while (index < BIT.length) {
        BIT[index] ^= val;
        index += index & -index;
    }
}

// Query Binary Indexed Tree (Fenwick Tree)
function queryBIT(BIT, index) {
    let xor = 0;
    while (index > 0) {
        xor ^= BIT[index];
        index -= index & -index;
    }
    return xor;
}

function xorRange(L, R) {
    // Build Fenwick Tree
    const BIT = new Array(R + 1).fill(0);
    for (let i = L; i <= R; i++) {
        updateBIT(BIT, i, i);
    }

    // Query Fenwick Tree
    const xorL = queryBIT(BIT, L - 1);
    const xorR = queryBIT(BIT, R);

    return xorL ^ xorR;
}

const L = 3;
const R = 6;
const result = xorRange(L, R);
console.log(`Bitwise XOR of all numbers from ${L} to ${R} is ${result}`);

Output:

Bitwise XOR of all numbers from 3 to 7 is 3

Time Complexity: O(NlogN) time, where N is the size of the range. Querying the Fenwick Tree takes O(logN) time.

Space Complexity: O(N) for storing the tree structure.

Compute the Bitwise XOR of all Numbers in a Range using JavaScript

The complexity of bitwise XOR computation for all the numbers in a specific range is the most frequent difficulty that many people face during the problem-solving process.

Problem Description: Given two integers, L and R, find the bitwise XOR of all numbers in the inclusive range from L to R. There are several approaches to computing the bitwise XOR of all numbers in a range using JavaScript which are as follows:

Table of Content

Bitwise XOR Property
Segment Trees
Binary Indexed Trees (Fenwick Trees)
Bitwise Manipulation

Tags:

#JavaScript #Web Technologies

Segment Trees

Bitwise Manipulation

Binary Indexed Trees (Fenwick Trees)

Compute the Bitwise XOR of all Numbers in a Range using JavaScript

Similar Reads